Merge Sort

Merge sort is the divide-and-conquer one. It splits the array in half, then splits each half again, all the way down to single values that are already sorted. Then it walks back up, merging each pair of sorted runs by lining them up and taking the smaller front value until both are empty. Do that all the way up and the whole thing is sorted.

The nice thing is it doesn’t care what you feed it. Sorted, reversed, or shuffled, it’s n log n every time, with no worst case to slump into like quick sort. Try Sorted or Reversed and watch the comparison count barely move. The catch is it needs room to copy the runs while it zips them, so you trade that steady speed for a whole extra array’s worth of space.

Hit Play to watch it run, or use Next and Back to step one move at a time. Shuffle deals a fresh array, the violet band is the chunk it’s splitting or merging right now, and the highlighted line shows you where the code is at each step.