Merge Sort

Spotting one

Three tells. You need sorting whose speed never degrades, whatever the input. You need equal items to keep their original order. Or you are counting pairs that are out of order with each other.

That third one surprises people, and it is the most interesting use on this page.

Merge sort or quick sort?

Merge sort is dependable and gentle. Same speed on every input, equal items keep their order, and it needs extra room to work.

Quick sort is usually quicker in practice and needs no extra room, but a bad pivot can make it dramatically slower and it scrambles equal items.

Sorting a linked list? Merge sort, comfortably. It never needs to jump to an arbitrary position the way quick sort does.

Where to start

Merge Two Sorted Arrays first. Combining two already sorted lists is the entire engine, and it is worth writing on its own before wrapping anything around it.

Sort an Array Using Merge Sort then puts the two halves around that engine. Sort List moves it onto a linked list.

Merge Intervals is not merge sort, but it belongs to the same habit of thought: sort first, then sweep through once.

Count Inversions is the real prize. The moment you take an item from the right half during a merge, you have learned it was out of order with everything still left in the left half, so you can count them all in one go instead of one at a time. Count of Smaller Numbers After Self and Merge k Sorted Lists take it further.

Common mistakes

Forgetting the leftovers. When one half runs out, everything still in the other half has to be copied across.

Breaking the stable order by taking from the right half when both sides are equal. Take from the left on a tie.

On the counting problems, counting one at a time instead of noticing the whole remaining left half counts in a single step.