Comparing Sorting Algorithms
Sorting is the process of rearranging a collection of elements into a defined order, usually ascending or descending. It sounds like a simple problem, but it is one of the most studied topics in computer science because so many other techniques depend on it: binary search needs a sorted array, deduplication is trivial once equal elements sit next to each other, and scheduling or merging problems often reduce to “sort, then sweep.” There is no single “best” sorting algorithm — the right choice depends on input size, how much memory you can spare, whether the data is nearly sorted already, and whether you need stability (preserving the relative order of equal elements). This lesson compares the major algorithms side by side so you can reason about which one fits a given situation, including in interviews.
Overview: How Sorting Algorithms Work
Almost every classic sorting algorithm is comparison-based: it decides the final order purely by comparing pairs of elements with <, >, or ==. A well-known result from information theory says that any comparison-based sort needs at least O(n log n) comparisons in the worst case, because there are n! possible orderings of n items, and each comparison can only cut the remaining possibilities roughly in half (log2(n!) is O(n log n)). This is why merge sort, quicksort, heap sort, and Python’s built-in sort all cluster around O(n log n), while it is mathematically impossible for a general-purpose comparison sort to reliably beat that bound.
The algorithms split into two broad families. The simple, quadratic sorts — bubble sort, insertion sort, selection sort — repeatedly scan the data and fix one element (or one inversion) at a time. They are easy to write correctly, sort in place with O(1) extra memory, and some of them (insertion sort especially) are genuinely fast on small or nearly-sorted input. The divide-and-conquer sorts — merge sort, quicksort, heap sort — split the problem into smaller pieces, sort the pieces, and combine the results, which is what gets them down to O(n log n). Python’s built-in sorted() and list.sort() use Timsort, a hybrid algorithm that runs insertion sort on small runs and merges those runs the way merge sort does, while also detecting and reusing already-sorted stretches of the input — which is why it does noticeably less work on partially-sorted real-world data than a naive O(n log n) sort would suggest.
Another axis that matters as much as speed is stability: a stable sort guarantees that if two elements compare as equal, they keep their original relative order after sorting. This matters whenever you sort by one key after already having sorted (or naturally ordered) by another — for example, sorting a list of orders by customer name after they are already sorted by timestamp, and wanting ties broken by the earlier timestamp. Merge sort, insertion sort, and Timsort are stable. The classic in-place quicksort and heapsort are not, because their swapping strategies can reorder equal elements.
Time and Space Complexity
The table below summarizes the algorithms covered in this course. n is the number of elements being sorted.
| Algorithm | Best | Average | Worst | Space | Stable? |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quicksort | 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 |
Timsort (Python’s sorted()) |
O(n) | O(n log n) | O(n log n) | O(n) | Yes |
The reasoning behind these numbers: bubble sort and insertion sort both do a single linear pass through nearly-sorted data with no swaps needed, which is where their O(n) best case comes from — but in the worst case (reverse-sorted input) every pair is out of order, forcing roughly n²/2 comparisons and swaps, hence O(n²). Selection sort has no early-exit shortcut — it always scans the remaining unsorted region to find the minimum, so it is O(n²) even on already-sorted input. Merge sort always splits the array in half (log n levels of recursion) and does O(n) work merging at each level, giving O(n log n) in every case, but it needs O(n) auxiliary space for the merge step because it cannot merge two sorted halves back together in place without extra storage. Quicksort’s average case is O(n log n) because a random or well-chosen pivot splits the array roughly in half each time, but if the pivot is consistently the smallest or largest element (for example, always picking the first element of an already-sorted array), each partition only shrinks by one, degrading to O(n²). Its space cost is the recursion stack, O(log n) on average.
Examples
Example 1: Bubble sort, and why it is safe on the caller’s list
Bubble sort repeatedly walks the array, swapping any adjacent pair that is out of order, so the largest remaining value “bubbles” to the end of the array on each pass. A swapped flag lets it stop early once a full pass makes no swaps — that early exit is what gives it its O(n) best case on already-sorted input.
def bubble_sort(arr: list[int]) -> list[int]:
n = len(arr)
arr = arr.copy()
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
numbers = [5, 2, 9, 1, 5, 6]
print("Original:", numbers)
print("Bubble sorted:", bubble_sort(numbers))
print("Original unchanged:", numbers)Output:
Original: [5, 2, 9, 1, 5, 6]
Bubble sorted: [1, 2, 5, 5, 6, 9]
Original unchanged: [5, 2, 9, 1, 5, 6]Notice that bubble_sort copies its input with arr.copy() before mutating it, so the caller’s original list is untouched — a small habit worth adopting for any sort that works by swapping in place, since surprising callers by mutating their data is a common source of bugs.
Example 2: Stability in action
Because Python’s sorted() is stable, sorting twice by two different keys, one after another, is a reliable way to do a multi-key sort: sort by the secondary key first, then by the primary key, and ties in the primary key will keep the secondary order.
students = [("Alice", "B"), ("Bob", "A"), ("Cara", "B"), ("Dan", "A"), ("Eve", "B")]
by_name = sorted(students, key=lambda s: s[0])
by_grade_then_name = sorted(by_name, key=lambda s: s[1])
print("Sorted by name:", by_name)
print("Sorted by grade, ties keep name order:", by_grade_then_name)Output:
Sorted by name: [('Alice', 'B'), ('Bob', 'A'), ('Cara', 'B'), ('Dan', 'A'), ('Eve', 'B')]
Sorted by grade, ties keep name order: [('Bob', 'A'), ('Dan', 'A'), ('Alice', 'B'), ('Cara', 'B'), ('Eve', 'B')]Within grade A, Bob comes before Dan because that was their order after the name sort; within grade B, Alice, Cara, and Eve keep their alphabetical order too. If sorted() were not stable, this trick would silently scramble ties, which is exactly the kind of bug that only shows up on real-world data with duplicate keys.
Example 3: Merge sort and quicksort agree with the built-in sort
def merge_sort(arr: list[int]) -> list[int]:
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: list[int], right: list[int]) -> list[int]:
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged
def quick_sort(arr: list[int]) -> list[int]:
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)
data = [8, 3, 7, 4, 9, 2, 6, 1]
print("Merge sort:", merge_sort(data))
print("Quick sort:", quick_sort(data))
print("Built-in sorted:", sorted(data))
print("All match:", merge_sort(data) == quick_sort(data) == sorted(data))Output:
Merge sort: [1, 2, 3, 4, 6, 7, 8, 9]
Quick sort: [1, 2, 3, 4, 6, 7, 8, 9]
Built-in sorted: [1, 2, 3, 4, 6, 7, 8, 9]
All match: TrueThe quick_sort shown here uses the readable “partition into three lists” style (elements less than, equal to, and greater than the pivot) rather than the classic in-place swap version. It is easier to trace by hand, but note it uses O(n) extra space per level because it builds new lists instead of partitioning the original array in place — the in-place version achieves the O(log n) space figure from the complexity table.
How It Works Step by Step
Tracing bubble_sort from Example 1 on [5, 2, 9, 1, 5, 6] shows exactly how the largest unsorted value moves to the end on every pass:
| Pass | What happens | Array after the pass |
|---|---|---|
| 1 | Compares (5,2)→swap, (5,9)→no swap, (9,1)→swap, (9,5)→swap, (9,6)→swap | [2, 5, 1, 5, 6, 9] |
| 2 | Compares (2,5)→no, (5,1)→swap, (5,5)→no, (5,6)→no | [2, 1, 5, 5, 6, 9] |
| 3 | Compares (2,1)→swap, (1,5)→no, (5,5)→no | [1, 2, 5, 5, 6, 9] |
| 4 | Compares (1,2)→no, (2,5)→no — no swaps at all, so swapped stays False |
[1, 2, 5, 5, 6, 9] (loop breaks early) |
Each pass needs one fewer comparison than the last, because the largest already-placed elements at the end never need to be re-examined — that shrinking comparison count is exactly what sums to n²/2 comparisons in the worst case.
Common Mistakes
Mistake 1: Off-by-one in the inner loop bound
It is tempting to write the inner loop as range(0, n - i) instead of range(0, n - i - 1). This looks harmless but makes the loop compare arr[j] against arr[j + 1] when j is the last valid index, reading one element past the end of the list:
def buggy_bubble_sort(arr: list[int]) -> list[int]:
n = len(arr)
for i in range(n):
for j in range(0, n - i): # bug: should be n - i - 1
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
buggy_bubble_sort([3, 1, 2])On the very first pass, when i = 0, j reaches n - 1, so the code tries to read arr[j + 1], which is arr[n] — out of range. This raises IndexError: list index out of range. The fix is to always stop the inner loop one short of the unsorted region’s end, since the comparison itself looks one index ahead:
def bubble_sort_fixed(arr: list[int]) -> list[int]:
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
print(bubble_sort_fixed([3, 1, 2]))Output:
[1, 2, 3]Mistake 2: Confusing list.sort() with sorted()
list.sort() sorts a list in place and returns None — it does not return the sorted list. Assigning its return value is a very common beginner mistake:
numbers = [5, 3, 1, 4, 2]
sorted_numbers = numbers.sort()
print(sorted_numbers)This prints None, because that is what numbers.sort() returns, even though numbers itself is now correctly sorted. If you need a new sorted list and want to keep the original untouched, use the built-in function sorted() instead, which always returns a new list and never mutates its argument:
numbers = [5, 3, 1, 4, 2]
sorted_numbers = sorted(numbers)
print(sorted_numbers)
print(numbers)Output:
[1, 2, 3, 4, 5]
[5, 3, 1, 4, 2]Best Practices
- Reach for Python’s built-in
sorted()orlist.sort()for real code — Timsort is stable, highly optimized in C, and adapts to partially-sorted input. Only implement a sort by hand for learning or when an interview specifically asks for it. - Use
list.sort()when you own the list and want to save memory (in place, no copy); usesorted()when you need to keep the original order intact or are sorting a non-list iterable. - Prefer the
key=argument over writing custom comparison logic —sorted(items, key=lambda x: x.price)is clearer and faster than manual comparisons. - If you need a multi-key sort with tie-breaking, rely on stability: either sort by a tuple key like
key=lambda x: (x.category, x.name), or perform successive stable sorts from least to most significant key. - Choose insertion sort (or rely on Timsort’s adaptive behavior) when the data is small or nearly sorted — its near-linear best case beats the constant overhead of a recursive divide-and-conquer sort at small sizes.
- Avoid a naive worst-case-prone quicksort (always picking the first or last element as pivot) on data that might already be sorted or reverse-sorted; use a randomized or median-of-three pivot, or just use the built-in sort.
- When sorting is on the critical path for very large datasets that don’t fit in memory, look into external merge sort rather than any in-memory algorithm covered here.
Practice Exercises
1. Implement selection sort. Write def selection_sort(arr: list[int]) -> list[int]: that, on each pass, finds the index of the minimum value in the unsorted remainder of the list and swaps it into place. Verify it produces the same result as sorted() on at least three test lists, including one with duplicate values.
2. Reasoning question. You have a list of 100,000 integers that is already sorted except for 5 new values appended at the end. Which algorithm from this lesson would you choose to re-sort it, and why? (Hint: think about which algorithms have an adaptive, near-O(n) best case on almost-sorted input, versus which ones always pay the full O(n log n) or O(n²) cost regardless of how sorted the input already is.)
3. Stability checker. Write a function that takes a list of (key, original_index) pairs, sorts it by key only using sorted(), and checks that for every group of equal keys, the original_index values stay in ascending order. Run it on a list where several keys repeat and confirm it reports the sort as stable.
Summary
- Comparison-based sorts cannot beat
O(n log n)in the worst case; that bound comes from the number of comparisons needed to distinguish amongn!possible orderings. - Bubble, insertion, and selection sort are
O(n²)average/worst case andO(1)extra space; bubble and insertion sort have anO(n)best case on nearly-sorted data thanks to early exits, but selection sort does not. - Merge sort is
O(n log n)in every case and stable, but needsO(n)extra space for merging. - Quicksort is
O(n log n)on average with onlyO(log n)space, but degrades toO(n²)on adversarial input (like an already-sorted array with a poorly chosen pivot), and the classic in-place version is not stable. - Python’s built-in
sorted()/list.sort()use Timsort: stable,O(n log n)worst/average case,O(n)best case on already-sorted or partially-sorted data, and almost always the right choice in production code. - Stability matters whenever you sort by multiple keys or need reproducible tie-breaking — check the table above before assuming an algorithm preserves equal-element order.
- Always distinguish
list.sort()(in place, returnsNone) fromsorted()(returns a new list, leaves the original untouched).
