Sorting algorithms: insertion sort, merge sort and quicksort

Sorting data is one of the most frequent operations: a ranking, a list of components by price, samples for computing the median, data before a binary search. And it is the ground on which the importance of an algorithm’s complexity shows best: with a million elements, a good algorithm takes a tenth of a second, a naive one hours. In this lesson we cover the elementary sorts, merge sort and quicksort, and the theoretical limit that cannot be beaten.

Bubble sort and insertion sort

Bubble sort: walk the array swapping adjacent pairs that are out of order; after each pass the largest element has reached the end, like a rising bubble. Up to passes of comparisons are needed: .

Insertion sort: build the sorted part one element at a time, inserting each new element in its place among those already sorted, the way you arrange playing cards in your hand.

void insertion_sort(int v[], int n)
{
    for (int i = 1; i < n; i++) {
        int x = v[i];
        int j = i - 1;
        while (j >= 0 && v[j] > x) {   /* shift the larger ones right */
            v[j + 1] = v[j];
            j--;
        }
        v[j + 1] = x;
    }
}

This too is in the worst case, but on nearly sorted data it is very fast, almost , and with few elements (up to a few dozen) it beats the more sophisticated algorithms. That is why libraries use it for small pieces.

Merge sort: divide and conquer

The idea is recursive:

1. split the array into two halves;
2. sort each half (recursively);
3. merge the two sorted halves into a single sorted sequence.

Merging two sorted sequences is easy: compare their first elements and take the smaller, until one of them runs out.

#include <string.h>

/* merges v[lo..mid-1] and v[mid..hi-1], already sorted, using tmp as scratch space */
static void merge(int v[], int tmp[], int lo, int mid, int hi)
{
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi) tmp[k++] = (v[i] <= v[j]) ? v[i++] : v[j++];
    while (i < mid) tmp[k++] = v[i++];
    while (j < hi)  tmp[k++] = v[j++];
    memcpy(v + lo, tmp + lo, (hi - lo) * sizeof v[0]);
}

void merge_sort(int v[], int tmp[], int lo, int hi)   /* sorts v[lo..hi-1] */
{
    if (hi - lo < 2) return;
    int mid = lo + (hi - lo) / 2;
    merge_sort(v, tmp, lo, mid);
    merge_sort(v, tmp, mid, hi);
    merge(v, tmp, lo, mid, hi);
}

Why it costs

At each level of the recursion the merges handle all elements in total, and there are levels, because the parts halve at each level. So the total work is proportional to . With : about operations against bubble sort’s . Merge sort is also stable (equal elements keep their original order), but it needs a scratch array as large as the one being sorted.

Quicksort

Choose an element, the pivot, and rearrange the array so the smaller elements are on the left and the larger on the right; then sort the two parts recursively. It needs no extra memory and, on average, it is the fastest in practice, . But if the pivot is always the smallest or largest (for example taking the first element of an already sorted array), the parts are unbalanced and the cost becomes . Serious implementations choose the pivot at random or as the median of three elements. The C standard library’s qsort often uses it, with a pointer to the comparison function:

#include <stdlib.h>

static int compare(const void *a, const void *b)
{
    int x = *(const int *)a, y = *(const int *)b;
    return (x > y) - (x < y);      /* -1, 0, 1 with no risk of overflow */
}

/* ... */
qsort(v, n, sizeof v[0], compare);

The theoretical limit

An algorithm that sorts only by comparing pairs of elements must tell apart all possible permutations, and each comparison has two outcomes: at least comparisons are needed in the worst case. By Stirling’s formula . So no comparison sort can do better than : merge sort is optimal.

The limit can be beaten only by exploiting the structure of the data. Counting sort sorts integers between 0 and by counting how often each value appears, in : the fastest way to build the histogram and the median of a 12-bit converter’s readings ().

Which to choose

Algorithm	Average case	Worst case	Extra memory	Stable
insertion				yes
merge sort				yes
quicksort				no
heapsort				no

In practice the library function is almost always used. On a microcontroller, with few elements and little memory, insertion sort is often the best choice: simple, with no recursion and no extra memory.