Merge sort

Merge sort splits the list in half, sorts each half, and merges the two sorted halves into one. It takes O(n log n) time on every input, and it is stable.

Merging two sorted lists

The key step is the merge. Given two sorted lists, the smallest value overall is at the front of one of them. Take it, and repeat.

Keep an index i into left and j into right. While both lists have values left, one pass of the merge does this:

if left[i] <= right[j]:      # <= keeps it stable
    out.append(left[i]); i += 1
else:
    out.append(right[j]); j += 1

When one list runs out, copy what is left of the other to the end of out. Each pass of the loop moves one value to out, so merging lists of total length n takes O(n) time. Using <= rather than < means that on a tie, the value from the left list goes first. That is what makes merge sort stable.

The whole sort

A list of 0 or 1 values is already sorted: return a copy of it. A longer list is split at its middle index, each half is sorted by a recursive call, and the two sorted halves are merged. Writing it is SORT-P2.

Why it is correct, by strong induction on the length (CORR-3): a list of 0 or 1 values is sorted. For a longer list, both halves are shorter, so the recursive calls return them sorted, and merging two sorted lists gives a sorted list of all the values.

Why it is n log n

The cost is T(n) = 2T(n/2) + n. BIGO-5 solved this with a recursion tree: log₂ n levels, with n work of merging on each level, so Θ(n log n): Θ means the cost grows exactly this fast, no faster and no slower. The split does not depend on the values, so this holds for every input: sorted, reversed or random.

Merge sort needs more memory. The merge writes into a new list, so merge sort needs O(n) extra space. In-place merging exists, but it is complicated and slower in practice.

Counting inversions while merging

An inversion is a pair of positions i < j with a[i] > a[j] (lesson 1). Counting them pair by pair is O(n²). Merge sort can count them while it merges, with no extra pass. When the merge takes right[j] while left[i] is still waiting, right[j] is smaller than left[i] and every value after it in left. Each of those pairs is an inversion, so add len(left) - i to the count.

Now try SORT-P2, Merge sort and SORT-P3, How far out of order.