Sorting algorithms: insertion sort, merge sort and quicksort

Sorting data is one of the most frequent operations in computing: customer lists by surname, orders by date, search results by relevance. In everyday practice almost nobody writes a sorting algorithm from scratch, because every language provides an excellent one. Studying them is still worthwhile: they teach ideas that come back everywhere, such as splitting a problem into parts, the trade-off between memory and speed, and the difference between average and worst case.

Insertion sort: sorting playing cards

Insertion sort works like someone arranging the cards in their hand: they take one card at a time and insert it in the right position among those already sorted.

def insertion_sort(a):
    for i in range(1, len(a)):
        current = a[i]
        j = i - 1
        while j >= 0 and a[j] > current:
            a[j + 1] = a[j]   # shift larger elements to the right
            j -= 1
        a[j + 1] = current
    return a

In the worst case, a list sorted in reverse, every element has to move all the way to the start: O(n²). But on nearly sorted data it is very fast, close to O(n), because each element moves only a little. That is why, despite its simplicity, it is also used inside modern algorithms to handle small segments.

Merge sort: divide and conquer

Merge sort applies a powerful strategy: split the problem into smaller subproblems, solve them and combine the results.

1. The list is split in half.
2. Each half is sorted, applying the same procedure recursively.
3. The two sorted halves are merged into a single sorted list.

Merging is the key step: given two sorted lists, you just repeatedly compare their first elements and take the smaller one.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    result, i, j = [], 0, 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
    return result + left[i:] + right[j:]

Merge sort is O(n log n) in every case: best, average and worst. The price is the extra memory for the temporary lists.

Quicksort: fast on average

Quicksort also splits the problem, but differently: it picks an element called the pivot and redistributes the others into two groups, those smaller and those larger than the pivot. Then it sorts the two groups recursively. No merge phase is needed, because at the end the groups are already in the right place.

On average it is O(n log n) and, in implementations that work directly on the array, very memory-efficient. Its weak spot is the worst case, O(n²), which happens when the pivot is systematically the smallest or largest element. A naive implementation that always picks the first element falls right into this trap with already sorted data. Robust versions choose the pivot randomly or as the median of a few samples.

Comparison

Stability, often forgotten

A sort is stable if it preserves the relative order of elements considered equal. It sounds like a detail, but it has practical consequences. Suppose you have a list of orders already sorted by date and want to sort it by customer: with a stable algorithm, each customer's orders stay in date order. This lets you sort by several criteria in successive passes, starting from the least important criterion.

What your language actually uses

In Python, sorted() and list.sort() use Timsort, an algorithm devised by Tim Peters (refined in more recent versions) that combines merge sort and insertion sort, taking advantage of already sorted runs found in real data. It is stable and O(n log n) in the worst case. Other languages use different hybrid variants, often quicksort for primitive types and stable algorithms for objects.

In practice:

orders.sort(key=lambda o: o.date)                 # by date
customers = sorted(customers, key=lambda c: (c.surname, c.name))

The key parameter is the idiomatic way to sort complex objects: you state which value to compare, and you can use tuples for several criteria.

When to write one

Almost never. Standard library implementations have been optimised and verified for years. It only makes sense to consider a custom sort in particular situations: data that does not fit in memory and must be sorted in blocks on disk, integer values within a narrow range (where techniques such as counting sort exist), or specific constraints of embedded systems.

In short

• Insertion sort is simple, O(n²), but very fast on nearly sorted data.
• Merge sort splits, sorts and merges: guaranteed O(n log n), at the cost of extra memory.
• Quicksort is fast on average but must be protected from the worst case with a good pivot choice.
• Stability lets you sort by several criteria in successive passes.
• In real work, use the standard library sort with the key parameter.