Sorting is one of the most-asked algorithm topics in coding interviews and the topic every developer uses daily (whether they realize it or not). This 2026 cheat sheet compares the 8 sorting algorithms that come up in interviews, real production systems, and BSIT capstone projects. For each: time complexity, space complexity, when to use it, when to avoid it, and a Python example you can paste and run.
Quick 2026 verdict
In production Python, always use sorted() or list.sort(). They run Timsort (O(n log n) worst case, O(n) best on nearly-sorted data). In interviews, know merge sort (O(n log n) stable) and quick sort (O(n log n) average) by heart, know bubble sort and insertion sort conceptually. Never write your own bubble sort in production code.
The comparison table (memorize this)
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes |
| Timsort (Python) | O(n) | O(n log n) | O(n log n) | O(n) | Yes |
Stable means equal elements keep their original order. Matters if you sort a list of tuples by one field and want ties broken by original order (e.g. sort students by grade, then by name).
Bubble sort (the one everyone teaches, no one uses)
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arr
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))Use for: teaching, tiny lists under 10 elements, debugging. Never use for: production code. Even at n=100, bubble sort is 500x slower than Timsort.
Insertion sort (surprisingly useful)
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arrUse for: small arrays (n < 50), nearly-sorted data (O(n) best case), the "insert one new element into a sorted list" pattern. Timsort actually uses insertion sort as a subroutine on small chunks.
Merge sort (the interview safe pick)
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return resultUse for: the "sort this efficiently" interview question when you want the safest answer. O(n log n) guaranteed, stable. Downside: O(n) extra space. If interviewer says "sort in place", switch to quick sort or heap sort.
Quick sort (the interview flashy pick)
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)Beautiful in Python thanks to list comprehensions. In production, quicksort's O(n²) worst case (already-sorted input, bad pivot choice) makes it risky. Mitigation: randomize the pivot OR use Timsort. Use for: interview flexing, when you know your data is random.
Heap sort (in-place O(n log n))
import heapq
def heap_sort(arr):
heap = arr[:] # copy so we do not mutate input
heapq.heapify(heap)
return [heapq.heappop(heap) for _ in range(len(heap))]Python's heapq module gives you heap operations for free. Use for: the "top k elements" pattern (which uses a heap of size k, not full sort), priority queues, when guaranteed O(n log n) matters more than stability.
Counting sort (the linear-time cheat)
def counting_sort(arr):
if not arr:
return []
min_val, max_val = min(arr), max(arr)
count = [0] * (max_val - min_val + 1)
for x in arr:
count[x - min_val] += 1
result = []
for i, c in enumerate(count):
result.extend([i + min_val] * c)
return resultBreaks the O(n log n) sorting lower bound because it does not compare elements. Use for: integer sorting where the range k is small (< 10 * n roughly). Never use for: arbitrary numbers, floats, strings.
Timsort (what Python actually runs)
Timsort is a hybrid of merge sort + insertion sort tuned for real-world data. Written by Tim Peters in 2002 for Python, adopted by Java 7 (java.util.Arrays.sort), Android SDK, Rust, and Swift. Highlights:
- O(n) best case on nearly-sorted data. Detects runs of already-sorted elements and preserves them.
- O(n log n) worst case guaranteed.
- Stable. Equal elements keep their order.
- Adaptive. Faster on partially sorted input than pure merge sort.
You get all this by writing sorted(my_list) or my_list.sort(). There is zero reason to write your own sort in Python for production code.
When to use which sort (decision tree)
- Any Python production code:
sorted()orlist.sort(). Done deciding. - Custom key or reverse:
sorted(items, key=lambda x: x.age, reverse=True). - Small array (n < 50): insertion sort has less overhead. Rarely worth worrying about.
- Integer array with small range: counting sort or radix sort can hit O(n).
- Top k elements only: heapq.nlargest / heapq.nsmallest. O(n log k) instead of O(n log n).
- Interview: safe answer: merge sort. O(n log n) guaranteed, stable.
- Interview: flashy answer: quick sort with 3-way partition + random pivot.
- Interview: "sort in place": heap sort or in-place quick sort.
Official documentation
Frequently Asked Questions
What is the fastest sorting algorithm?
For general data: no algorithm is faster than O(n log n) using comparisons. In practice, Timsort is fastest on real-world data because it detects existing sorted runs. For special cases (small integer range) counting sort or radix sort hit O(n) by not comparing at all.
Why is quicksort O(n²) worst case?
If your pivot always ends up as the smallest or largest element, each partition step splits the array into a group of 0 and a group of n-1. That is n levels of recursion with n work per level = O(n²). Happens with already-sorted input and a naive "first element" pivot choice. Fix: pick pivot randomly or use the median-of-three heuristic.
What does "stable sort" mean?
A sort is stable if equal elements keep their original relative order. If you sort a list of (name, age) tuples by age, a stable sort preserves the original name-order among people with the same age. Python's sorted() is stable, so multi-key sorting works by chaining sorts: sort by name first, then by age, and ties in age keep the name-order.
Do I need to memorize all these for interviews?
Memorize the table (complexity + stability). Know how to CODE merge sort and quick sort from scratch (interviewers love asking). Know that Python's built-in is Timsort. Bubble and selection sort are only concept-check questions, not "code it" questions.
How does Timsort achieve O(n) best case?
Timsort scans the input for "runs" of already-sorted elements. If the entire array is one big run, it terminates in one pass = O(n). On nearly-sorted data with a few out-of-order elements, it merges small runs efficiently. Adaptive algorithms like this are why real production sorting is often much faster than textbook analysis suggests.
Can I sort in place in Python?
Use list.sort() instead of sorted(). list.sort() modifies the list in place and returns None. sorted() returns a new sorted list without touching the original. Same Timsort under the hood, different memory characteristics.
Related DSA + Interview tutorials
- Big-O Notation Complete Guide for Beginners 2026
- DSA Roadmap for BSIT Students 2026
- Recursion Explained with Real Examples 2026
- HashMap Deep Dive 2026 Python + Java + JavaScript (coming this week)
Official documentation
Glay Eliver
Programmer & Technical Writer at PIES IT Solution
Glay Eliver is a programmer and writer at PIES IT Solution, author of over 600 tutorials at itsourcecode.com. Specializes in JavaScript tutorials, Microsoft Office how-tos (Excel, Word, PowerPoint), and Python error debugging covering ImportError, TypeError, AttributeError, ModuleNotFoundError, and JavaScript ReferenceError. Authored several of the site's highest-traffic Excel and MS Office reference articles.
Expertise: JavaScript · MS Excel · MS Word · MS PowerPoint · Python · Python ImportError · Python TypeError · Python AttributeError · ModuleNotFoundError · JavaScript ReferenceError · Pygame · View all posts by Glay Eliver →