Merge Sort

Split, sort, merge

Merge sort uses the divide-and-conquer approach. The array is split in half, each half is sorted in the same way, and then the two already sorted parts are combined into one. The main work happens during the merge step.

static void merge(int[] a, int left, int mid, int right, int[] tmp) {
    int i = left;
    int j = mid;
    int k = left;

    while (i < mid && j < right) {
        tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
    }
    while (i < mid) tmp[k++] = a[i++];
    while (j < right) tmp[k++] = a[j++];

    for (int p = left; p < right; p++) {
        a[p] = tmp[p];
    }
}

Because both parts are already sorted, we only need to look at their current first unprocessed elements. The smaller one is copied into the temporary array, and the corresponding pointer moves forward. Every element participates in one merge at each level of the split.

Where O(n log n) comes from

At every recursion level, a total of O(n) elements is processed, and there are O(log n) levels because the problem size is roughly halved each time. The total running time is therefore O(n log n) regardless of the original data order.

The cost of predictable speed

A typical array implementation needs an auxiliary array of size O(n). This is an important difference from sorts that rearrange elements only inside the original array. In return, merge sort keeps predictable running time even when the input order is unfavorable.