Sorting Algorithms

Why sorting deserves its own deep dive#

Sorting — putting a collection into order — is probably the single most-studied problem in all of computer science. Not because arranging numbers is inherently fascinating, but because it's the perfect training ground for comparing algorithmic strategies head-to-head: every sorting algorithm solves the exact same problem, which makes the differences between strategies impossible to hide behind "well, they're solving different things." You're about to see three algorithms, three completely different core ideas, and three different Big-O results — all producing the identical, correct, sorted output.

Bubble sort: the simplest idea, O(n²)#

Analogy: imagine a line of people who need to stand in order of height. You walk down the line comparing each adjacent pair, swapping them if they're in the wrong order, then walk down the line again, and again, until an entire pass produces no swaps at all. With every pass, the largest remaining value "bubbles up" toward the end of the line.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):        # the unsorted portion shrinks by one each pass
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:                       # no swaps this pass means it's already sorted
            break
    return arr

print(bubble_sort([5, 2, 4, 1, 3]))   # [1, 2, 3, 4, 5]

Tracing the first pass on [5, 2, 4, 1, 3]: compare 5, 2 → swap → [2, 5, 4, 1, 3]; compare 5, 4 → swap → [2, 4, 5, 1, 3]; compare 5, 1 → swap → [2, 4, 1, 5, 3]; compare 5, 3 → swap → [2, 4, 1, 3, 5]. Notice 5, the largest value, has bubbled all the way to the end after just one pass — exactly what the analogy predicts.

Each pass compares up to n adjacent pairs, and up to n passes may be needed before the list is fully sorted, giving O(n²) time in the worst and average case — the same nested-loop-over-the-same-data shape flagged back in the introduction page. Space is O(1): bubble sort rearranges the array in place, needing no extra structures. In practice, bubble sort is essentially never used in production — it's taught because "keep swapping adjacent out-of-order pairs until nothing's left to swap" is about the most intuitive possible entry point into what a sorting algorithm even is.

Merge sort: divide and conquer, O(n log n)#

Merge sort takes a completely different approach: instead of nudging elements into place through many small local swaps, split the list in half, recursively sort each half, then merge the two already-sorted halves back into one.

Analogy: imagine combining two already-sorted decks of playing cards into one sorted deck. You don't need to re-sort anything — just compare the top card of each deck, take whichever is smaller, and repeat until both decks are empty. That merge step is fast and simple precisely because each half arrives already sorted.

def merge_sort(arr):
    if len(arr) <= 1:                 # base case: a list of 0 or 1 items is already sorted
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])      # recursively sort the left half
    right = merge_sort(arr[mid:])     # recursively sort the right half

    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:])           # append whatever's left over in either half
    result.extend(right[j:])
    return result


print(merge_sort([5, 2, 4, 1, 3]))   # [1, 2, 3, 4, 5]

Tracing it: [5, 2, 4, 1, 3] splits into [5, 2] and [4, 1, 3]. [5, 2] splits into [5] and [2] (both base cases) and merges to [2, 5]. [4, 1, 3] splits into [4] and [1, 3]; [1, 3] splits into [1] and [3] and merges to [1, 3]; then merge([4], [1, 3]) compares 4 vs 1 (take 1), then 4 vs 3 (take 3), then appends the leftover 4, giving [1, 3, 4]. Finally, merge([2, 5], [1, 3, 4]) compares 2 vs 1 (take 1), 2 vs 3 (take 2), 5 vs 3 (take 3), 5 vs 4 (take 4), then appends the leftover 5, giving [1, 2, 3, 4, 5].

Splitting the list in half takes O(log n) levels of recursion (each level halves what's left), and merging all the pieces back together at each level costs O(n) total work (every element gets touched exactly once per level, across all the merge calls happening at that level combined). O(log n) levels × O(n) work per level gives O(n log n) total — merge sort's time complexity in the best, average, and worst case alike, unlike bubble sort, whose worst case is much worse than its best. The cost is O(n) extra space, since merging needs a fresh array to write results into — merge sort is not in-place. One more property worth naming: merge sort is stable — if two elements are equal, they keep their original relative order, since the merge step always prefers the left side on ties (left[i] <= right[j]).

Quicksort: partitioning, average O(n log n)#

Quicksort also divides and conquers, but around a different core operation: partitioning. Pick a pivot element, then rearrange the array so everything smaller than the pivot ends up to its left and everything larger ends up to its right — the pivot itself lands in its final sorted position in a single pass. Then recursively partition the left and right sections the same way.

def quicksort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1

    if low < high:
        pivot_index = partition(arr, low, high)
        quicksort(arr, low, pivot_index - 1)       # sort everything left of the pivot
        quicksort(arr, pivot_index + 1, high)      # sort everything right of the pivot

    return arr


def partition(arr, low, high):
    pivot = arr[high]              # choose the last element as the pivot
    i = low - 1                    # boundary of the "confirmed smaller than pivot" region

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]   # place the pivot in its final position
    return i + 1


print(quicksort([5, 2, 4, 1, 3]))   # [1, 2, 3, 4, 5]

Tracing the first partition([5, 2, 4, 1, 3], 0, 4): pivot is arr[4] = 3, i starts at -1. j=0, arr[0]=5: not <= 3, skip. j=1, arr[1]=2: <= 3, so i becomes 0 and we swap arr[0]/arr[1] → [2, 5, 4, 1, 3]. j=2, arr[2]=4: not <= 3, skip. j=3, arr[3]=1: <= 3, so i becomes 1 and we swap arr[1]/arr[3] → [2, 1, 4, 5, 3]. Loop ends; swap arr[i+1] (arr[2]) with arr[high] (arr[4]) → [2, 1, 3, 5, 4], and partition returns 2. The pivot 3 is now sitting at index 2, with everything left of it (2, 1) <= 3 and everything right of it (5, 4) > 3 — exactly what partitioning promises. Quicksort then recurses independently on [0, 1] and [3, 4] until the whole array is sorted.

Average case: when the pivot roughly splits the array in half each time (like merge sort), you get O(log n) levels of recursion with O(n) partitioning work per level, giving O(n log n). Worst case: if the pivot happens to be the smallest or largest remaining element every single time — which happens on already-sorted (or reverse-sorted) input with this "always pick the last element" pivot strategy — partitioning does O(n) work but only peels off one element per level, giving O(n) levels × O(n) work = O(n²). Real-world quicksort implementations guard against this by picking a random pivot or a "median of three" estimate instead of always trusting the last element, making the worst case exceedingly unlikely to trigger by accident.

Space is O(log n) on average — just the recursion stack, since partitioning rearranges the array in place with no extra arrays needed. That's quicksort's practical edge over merge sort's O(n) space requirement, which is a big part of why quicksort tends to be preferred in general-purpose libraries despite its worst-case risk. Quicksort is not stable — the swaps during partitioning can reorder equal elements relative to each other.

Comparing all three#

"Stable" matters more often than it first appears: if you sort a guest list by last name and it's already sorted by first name, a stable sort guarantees people who share a last name stay in their original first-name order — an unstable sort makes no such promise, and could silently scramble that secondary ordering.

When to just use Python's sorted() / Timsort#

Python's built-in sorted() and list.sort() use Timsort — a hybrid of merge sort and insertion sort, specifically engineered to exploit runs of already-sorted (or reverse-sorted) data that show up constantly in real-world input. It guarantees O(n log n) worst-case time, is stable, and is implemented in highly optimized C — no hand-written Python loop is going to out-perform it.

people = [("Sam", 22), ("Ava", 19), ("Max", 22)]

# sort by age; people with equal ages keep their original relative order (stability)
people_sorted = sorted(people, key=lambda person: person[1])
print(people_sorted)   # [('Ava', 19), ('Sam', 22), ('Max', 22)]

In real production code, reach for sorted()/.sort() by default, every time. Implementing bubble sort, merge sort, or quicksort by hand is genuinely valuable for building the intuition this page is teaching — recognizing why one algorithm beats another, and being ready to explain the trade-offs in an interview — but it's rarely the right engineering choice for actual application code, where Timsort has already done the work better than a hand-rolled version reasonably could.

Common mistakes#

• Off-by-one errors in the partition/pivot logic. Quicksort's partitioning is notoriously easy to get subtly wrong — always trace a small example by hand (like the one above) before trusting a new implementation.
• Forgetting merge sort's merge step is where the real work happens. The recursive splitting alone doesn't sort anything — it's the merge that actually combines two sorted halves into a larger sorted whole.
• Assuming quicksort's worst case "won't happen in practice" and then feeding it already-sorted input with a naive last-element pivot — precisely the input shape that triggers O(n²).
• Reimplementing sorting when sorted(key=...) already solves the problem, or writing a manual comparison loop instead of passing a key function.
• Ignoring stability when it matters — sorting by one field and then needing an earlier sort's order preserved for ties requires a stable algorithm (or a single sort with a composite key), not an unstable one.