Sorting Algorithms: Bubble, Insertion, Merge, Quick, Heap

Sorting is the canonical algorithms topic — not because real programs sort their own data (they don’t), but because the five classical sorts each demonstrate a different design idea: incremental, divide-and-conquer, and selection-from-a-heap. Knowing them gives you a vocabulary for the rest of algorithms.

This post tours all five with the smallest code that is still correct, plus the rule you should actually follow in real code: call the language’s sort().

Quick comparison

Stable means equal elements keep their relative order — important when sorting records by a secondary key.

Bubble sort

The idea: repeatedly walk the array, swapping adjacent out-of-order pairs. The largest element “bubbles” to the end on each pass.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(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([5, 2, 4, 1, 3]))
# output: [1, 2, 3, 4, 5]

Time: O(n^2) average and worst, O(n) best (already sorted, the swapped short-circuit). Space: O(1). Stable.

Use case in production: essentially none. It’s a teaching tool.

Insertion sort

The idea: build a sorted prefix one element at a time. For each new element, slide it left until it sits in the right place.

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 arr

print(insertion_sort([5, 2, 4, 1, 3]))
# output: [1, 2, 3, 4, 5]

Time: O(n^2) average and worst, O(n) best. Space: O(1). Stable.

Insertion sort is surprisingly useful for small arrays (n < ~16). Real implementations of merge sort and quicksort fall back to it for tiny subarrays.

Merge sort

The idea: split the array in half, sort each half recursively, then merge the two sorted halves.

[5, 2, 4, 1, 3, 6]
/              

[5, 2, 4]         [1, 3, 6]
/    \             /    

[5, 2]  [4]        [1, 3]  [6]
/   \              /   

[5]  [2]           [1]  [3]
\   /              \   /
[2, 5]             [1, 3]
\    /             \    /
[2, 4, 5]         [1, 3, 6]
\              /
[1, 2, 3, 4, 5, 6]

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(a, b):
    out = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    out.extend(a[i:])
    out.extend(b[j:])
    return out

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

Time: O(n log n) in all cases. Space: O(n) (the auxiliary buffers). Stable.

The <= in if a[i] <= b[j] is what makes it stable — equal elements from the left half are placed first.

Quick sort

The idea: pick a pivot, partition the array into “less than pivot” and “greater than pivot”, recurse on each side.

input:  [ 5,  2,  4,  1,  3,  6 ]   pivot = 4 (last element… oops, pick 4)
Let’s pivot = arr[2] = 4 and partition:
scan with i (boundary) and j (cursor):
j=0: 5 > 4, leave            [ 5,  2,  1,  3,  6 ]   i=0
j=1: 2 < 4, swap arr[i],arr[j] -> [ 2,  5,  1,  3,  6 ]   i=1
j=2: 1 < 4, swap                 [ 2,  1,  5,  3,  6 ]   i=2
j=3: 3 < 4, swap                 [ 2,  1,  3,  5,  6 ]   i=3
j=4: 6 > 4, leave                                       i=3
place pivot at i:    [ 2,  1,  3,  4,  5,  6 ]
^
pivot in final spot
now recurse on [2, 1, 3] and [5, 6]

def quick_sort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo < hi:
        p = partition(arr, lo, hi)
        quick_sort(arr, lo, p - 1)
        quick_sort(arr, p + 1, hi)
    return arr

def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i

print(quick_sort([5, 2, 4, 1, 3, 6]))
# output: [1, 2, 3, 4, 5, 6]

Time: O(n log n) average, O(n^2) worst (already sorted with the naive last-element pivot). Space: O(log n) recursion stack. Not stable.

Production quicksorts pick the pivot with median-of-three or randomly to avoid the O(n^2) worst case on adversarial inputs.

Heap sort

The idea: build a max-heap of the array, then repeatedly pop the max to the end.

import heapq

def heap_sort(arr):
    # heapq is a min-heap; negate to use as max-heap, or pop into a new list
    h = arr[:]
    heapq.heapify(h)
    return [heapq.heappop(h) for _ in range(len(h))]

print(heap_sort([5, 2, 4, 1, 3, 6]))
# output: [1, 2, 3, 4, 5, 6]

Time: O(n log n) in all cases. Space: O(1) if done in place (Python’s heapq is in place on the heap, but our convenience version above allocates O(n)). Not stable.

Heap sort’s selling point is guaranteed O(n log n) with O(1) extra space — quicksort can spike to O(n^2), merge sort needs O(n) aux. Its downside is poor cache behaviour, which makes it slower in practice than a tuned quicksort.

So which one should you use?

In real code: none of them. Use the language’s built-in sort:

arr = [5, 2, 4, 1, 3, 6]
arr.sort()                # in place
sorted_copy = sorted(arr) # returns a new list

Python’s list.sort is Timsort — a hybrid of merge sort and insertion sort that is O(n log n) worst case, stable, and exploits already-sorted runs in the input. It is faster and more correct than anything you will write by hand in an interview.

The same is true in JavaScript (Array.prototype.sort), Java (Arrays.sort and List.sort), and Go (slices.Sort). Every mainstream language ships a well-tuned hybrid sort.

You implement these algorithms because:

1. Interviews ask about them.
2. Understanding their structure unlocks downstream algorithms (heap sort → priority queues; merge sort → external sorting; quicksort → quickselect).
3. They are the cleanest examples of three design paradigms — incremental, divide-and-conquer, and selection.

Stability — when does it matter?

Stable sort: equal keys keep their input order. Consider sorting a list of (name, age) tuples by age:

people = [("Alice", 30), ("Bob", 25), ("Carol", 30), ("Dave", 25)]
people.sort(key=lambda p: p[1])
print(people)
# output: [('Bob', 25), ('Dave', 25), ('Alice', 30), ('Carol', 30)]

Alice came before Carol in the input and still does in the output — that is stability at work. You rely on it whenever you sort by multiple keys via successive sorts: sort by the least significant key first, then the most significant.

Recap

You now know:

• Bubble and insertion are O(n^2) — teaching tools, plus insertion is great for tiny inputs.
• Merge sort is O(n log n) everywhere, stable, but needs O(n) extra space.
• Quick sort is O(n log n) average, O(n^2) worst, in place, not stable.
• Heap sort is O(n log n) always, O(1) extra space, not stable.
• Stability matters when sorting by multiple keys or preserving input order.
• In real code, use the built-in sort — it is Timsort or similar.

Next steps

Sorting and binary search are the two halves of the same coin. Once an array is sorted, binary search reduces lookups from O(n) to O(log n).

→ Next: Binary Search — The Pattern That Powers a Hundred Problems

Questions or feedback? Email codeloomdevv@gmail.com.