Sorting algorithms explained: insertion, merge and quick sort with timings

Sorting is the classic interview topic, and it teaches ideas you will meet everywhere: divide and conquer, trade-offs between time and memory, and what "stable" means. In real projects you will almost always call the built-in sort, but understanding the algorithms tells you why it is fast and which behaviour to expect. The code and timings below were run with Python 3 before publishing.

The three algorithms

Insertion sort. Keep the left part sorted. Take the next item and slide it left until it fits, like sorting playing cards in your hand. Simple, O(n²) in the worst case, but close to O(n) if the data is already nearly sorted.

Merge sort. Split the list in half, sort each half (recursively), then merge two sorted halves by repeatedly taking the smaller front item. Always O(n log n), but it needs O(n) extra memory.

Quick sort. Pick a pivot, move smaller items to one side and larger to the other, then sort each side. O(n log n) on average, in place, usually very fast in practice. The worst case is O(n²) when pivots are consistently bad, for example always taking the first item of already sorted data. Choosing a random pivot makes that unlikely.

A working example

Save as sorting.py:

import random
import time


def insertion_sort(a):
    a = list(a)
    for i in range(1, len(a)):
        x, j = a[i], i - 1
        while j >= 0 and a[j] > x:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = x
    return a


def merge_sort(a):
    if len(a) <= 1:
        return list(a)
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= keeps equal items in original order (stable)
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]


def quick_sort(a):
    a = list(a)

    def go(lo, hi):
        while lo < hi:
            p = a[random.randint(lo, hi)]  # random pivot avoids the sorted-input trap
            i, j = lo, hi
            while i <= j:
                while a[i] < p: i += 1
                while a[j] > p: j -= 1
                if i <= j:
                    a[i], a[j] = a[j], a[i]
                    i += 1; j -= 1
            # recurse into the smaller side, loop on the larger: stack stays O(log n)
            if j - lo < hi - i:
                go(lo, j); lo = i
            else:
                go(i, hi); hi = j

    go(0, len(a) - 1)
    return a


def timed(fn, data):
    t = time.perf_counter()
    fn(data)
    return (time.perf_counter() - t) * 1000


if __name__ == "__main__":
    random.seed(1)
    n = 3000
    inputs = {
        "random": [random.randint(0, 10**6) for _ in range(n)],
        "already sorted": list(range(n)),
        "reversed": list(range(n, 0, -1)),
    }
    print(f"n = {n}, milliseconds (one run each)")
    print(f"{'input':<16}{'insertion':>11}{'merge':>9}{'quick':>9}{'sorted()':>10}")
    for name, data in inputs.items():
        row = [timed(f, data) for f in (insertion_sort, merge_sort, quick_sort, sorted)]
        print(f"{name:<16}{row[0]:>11.2f}{row[1]:>9.2f}{row[2]:>9.2f}{row[3]:>10.2f}")

    print()
    people = [("Asha", 30), ("Bijoy", 25), ("Chitra", 30), ("Dipu", 25)]
    print("stable by age  :", sorted(people, key=lambda p: p[1]))

Output of python3 sorting.py (3,000 numbers, one run each; exact times depend on the machine):

n = 3000, milliseconds (one run each)
input             insertion    merge    quick  sorted()
random               576.29    14.41     9.21      0.79
already sorted         0.61     9.24     6.39      0.05
reversed             929.60    11.50     7.43      0.08

stable by age  : [('Bijoy', 25), ('Dipu', 25), ('Asha', 30), ('Chitra', 30)]

Reading the timings

• Random data: insertion sort took 576 ms, merge sort about 14 ms, quick sort about 9 ms. At just 3,000 items, O(n²) is already roughly 40 to 60 times slower. At 300,000 items the gap would be unbearable.
• Already sorted: insertion sort wins among the three hand-written ones (0.61 ms), because it only checks each item once and never moves anything. This is why insertion sort is used inside serious sorting routines for small or nearly sorted pieces.
• Reversed: insertion sort's worst case (930 ms): every item slides all the way to the front.
• sorted() is faster than all of them, even though our code is plain Python and it is not magic: it is written in C and uses an algorithm that exploits existing order.

What "stable" means

A sort is stable if items that compare equal keep their original relative order. Look at the last line: sorting people by age kept Asha before Chitra and Bijoy before Dipu, as in the input. That matters when you sort by one key and then another (for example by city, then by age). Merge sort is stable (the <= in the merge step is what guarantees it). Typical in-place quick sort is not stable. Python's built-in sort is stable, which is documented behaviour you can rely on.

What Python actually uses

sorted() and list.sort() use Timsort, a hybrid of merge sort and insertion sort that finds already ordered runs in the data and merges them. It is O(n log n) in the worst case and close to O(n) on nearly sorted data, which is why the "already sorted" row is so fast. JavaScript's Array.prototype.sort has been required to be stable since ES2019; the algorithm depends on the engine.

Tests

Save as test_sorting.py:

import random
import unittest

from sorting import insertion_sort, merge_sort, quick_sort

ALGOS = (insertion_sort, merge_sort, quick_sort)


class SortTests(unittest.TestCase):
    def test_matches_builtin_on_random_data(self):
        rnd = random.Random(7)
        for _ in range(200):
            data = [rnd.randint(-50, 50) for _ in range(rnd.randint(0, 60))]
            for f in ALGOS:
                self.assertEqual(f(data), sorted(data), f.__name__)

    def test_edge_cases(self):
        for f in ALGOS:
            self.assertEqual(f([]), [])
            self.assertEqual(f([1]), [1])
            self.assertEqual(f([2, 2, 2]), [2, 2, 2])
            self.assertEqual(f(list(range(1000, 0, -1))), list(range(1, 1001)))

    def test_input_not_modified(self):
        data = [3, 1, 2]
        for f in ALGOS:
            f(data)
            self.assertEqual(data, [3, 1, 2])


if __name__ == "__main__":
    unittest.main()

$ python3 -m unittest -v
Ran 3 tests in 0.162s

OK

We compare every algorithm against sorted() on 200 random lists (including empty ones and many duplicates), check edge cases, and confirm the input list is not modified. Checking a new algorithm against a trusted one on random data is a very effective testing habit.

Which one when?

• In real code: use the built-in sort. Do not write your own.
• Interview or learning: know merge sort (clean, guaranteed O(n log n), stable) and quick sort (average-case champion, in place), and be able to explain the worst cases.
• Small or nearly sorted data: insertion sort is fine, which is why libraries use it for small pieces.
• Limited memory, no stability needed: in-place sorts like quick sort or heap sort.
• Integers in a small range: counting or radix sort can beat O(n log n), because they do not compare items.

A well-known fact: any sort that works only by comparing items needs at least about n log n comparisons in the worst case. That is why O(n log n) is the target for general sorting.

Common mistakes

• Choosing a bad pivot, such as always the first item, and hitting O(n²) on sorted input.
• Forgetting stability when sorting by several keys.
• Sorting repeatedly inside a loop instead of once, or sorting just to find the minimum (use min, O(n)).
• Modifying the input list when the caller does not expect it.
• Writing a custom sort for production instead of using the library.
• Using an unsuitable comparison function that is inconsistent, which can give wrong results or errors.

Main idea: insertion sort is simple and great for small or nearly sorted data, merge sort is a safe O(n log n) and stable, quick sort is fast on average with a good pivot. In real projects, use the built-in sort, and use these algorithms to understand why it behaves as it does.

---

Interview prep and DSA series, Part 3 (more algorithms): 1 of 5.