Comparisons
Writes
Merges

  • Part being merged
  • Compared
  • Written back
  • Merged so far

More about merge sort

Merge sort

Merge sort is a divide-and-conquer algorithm. It splits the list in half, sorts each half the same way, and merges the two sorted halves by repeatedly taking the smaller front value. Watch the halves lifted into a buffer row and written back in order, at any speed or one step at a time, and count comparisons, writes, and merges. Press Play to watch the sort, or Step and Back to go one step at a time. Drag the step slider to jump anywhere. The tiles count comparisons, writes back into the list, and merges. Choose how many bars, how they start, or type your own numbers. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.

How it works

  1. Choose how many bars and how they start: random, nearly sorted, reversed, or with few unique values. Or type your own numbers.
  2. Press Play, or use Step and Back to move one step at a time. Drag the step slider to jump anywhere in the sort.
  3. Watch each merge: the two sorted halves go down into the buffer, and the smaller front value goes back up, one at a time.

How merge sort works

A single value is already sorted. For anything longer, split the list into two halves and sort each half with merge sort. Then merge them: look at the front value of each half, move the smaller one into the result, and repeat until both halves are empty. Because both halves are sorted, the result is sorted too.

Always n log n

Splitting in half again and again gives about log₂ n levels, and each level of merges writes every value once, so the sort makes about n log₂ n writes, and at most as many comparisons. Unlike bubble, selection and insertion sort, that does not grow with n², and the order of the list matters far less. The cost is a buffer as long as the list. Merge sort is also stable, which is why it is the basis of the sorts in Python and Java.

Frequently asked questions

How does merge sort work?

It splits the list in half, sorts each half with merge sort, and merges the two sorted halves by repeatedly taking the smaller of their front values. A list of one value is already sorted, so the splitting stops there.

How many comparisons does merge sort make?

At most about n log₂ n − n + 1, and at least about half of n log₂ n, for n values. For 40 values that is at most 177. The writes back into the list are always the same for a given n: one per value at each level of merging.

Why does merge sort need extra memory?

Merging two halves in place is hard to do quickly, so the usual merge sort copies the halves into a buffer and writes them back in order. The buffer is as long as the list, which is the main drawback compared with quicksort and heap sort.

Is merge sort stable?

Yes. When the two front values are equal, the one from the left half goes first, so equal values keep their original order.

Are my numbers sent anywhere?

No. The sort runs in your browser, and your last settings stay in this browser's local storage.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Go to Editor