Merge sort & quicksort

Take two sorted piles of cards, face up. The smallest card overall is on top of one of the two piles, so compare the two top cards, take the smaller, and repeat. When one pile runs out, the rest of the other goes on the end. Every card is placed after one comparison at most: merging n items takes O(n).

Taking from the left pile when the two top cards are equal keeps equal items in their original order, which is what makes merge sort stable.

Merge sort is divide and conquer with all the work in the combine step. Split the range in half, sort each half the same way, merge the two sorted halves. A range of one item is already sorted, which is the base case.

Every level of the recursion tree merges all n items once, and halving gives about log₂ n levels: O(n log n), on every input, sorted or shuffled. That is the T(n) = 2T(n ÷ 2) + O(n) row of Divide & conquer.

The cost is memory: merging needs a buffer to collect the merged items, O(n) extra space. In return merge sort is predictable, stable, and good at data that arrives as a stream or doesn't fit in memory, since merging only ever reads each run from front to back.

Quicksort does its work while splitting. Pick one item, the pivot, and rearrange the range so every smaller item comes before it and every other item after it. That rearranging is the partition. The pivot is now exactly where it belongs in the sorted list, and the two sides can be sorted separately, with nothing to combine afterward.

The partition above keeps a boundary i: everything left of it is smaller than the pivot. Each item that is smaller gets swapped across the boundary, and the boundary moves one cell right. One pass, O(n), in place: no buffer needed.

After a partition the pivot is exactly where sorting would put it. To find the item that belongs at one particular index, you only need the side that contains that index: recurse into one side and forget the other. On average each step halves the range, so the work is n + n/2 + n/4 + … ≈ 2n: O(n), cheaper than sorting. A bad pivot makes it O(n²), as in quicksort, so real code picks the pivot at random.

A pivot near the middle value splits the range into two near-equal halves: about log₂ n levels, O(n log n). A pivot that is the smallest or largest item splits off nothing: the other side has n − 1 items, and repeated at every level that is n levels of O(n) work, O(n²).

The simple rule used above, "the last item is the pivot", hits that worst case on a list that is already sorted, which is a common input. Two standard fixes:

• pick the pivot at random, so no particular input is reliably bad, and the expected time is O(n log n) on every input;
• take the median of three items, such as the first, middle and last, which avoids the sorted-input trap.

Every sort so far is a comparison sort: it learns about the items only by comparing two of them. A list of n distinct items can arrive in any of n! orders, and the sort has to tell them all apart, since each needs different moves. Each comparison has two outcomes, so k comparisons can tell at most 2ᵏ cases apart. Telling n! cases apart needs at least log₂(n!) comparisons, and log₂(n!) grows like n log₂ n.

So merge sort is as good as comparison sorting gets, up to a constant. Beating O(n log n) means not comparing at all, which is what Linear-time sorting does for keys of a known, limited range.

Real libraries combine them with insertion sort for small pieces. Python's sort and Java's sort for objects are merge-based and stable. Java's sort for primitive numbers is a quicksort variant with two pivots, where stability doesn't matter. C++'s std::sort is a quicksort that switches to a guaranteed O(n log n) method if the recursion gets too deep, so the O(n²) worst case can't happen.