How merge sort works
- Split the array in the middle. Keep splitting each half until every part holds one value.
- A part with one value is already sorted.
- Merge two sorted neighbours: copy them into two temporary arrays, then keep taking the smaller of the two front values and writing it back.
- When one temporary array runs out, copy what is left of the other. The merges continue upwards until one covers the whole array.
What the colours mean
The bright bars are the part being split or merged. Under the bars are the two temporary arrays: yellow cells are the pair being compared, a pink cell is the value written back, and faded cells are used up. Pale green parts are sorted but still have a merge ahead of them.
Merge Sort time and space complexity
| Best case | Average case | Worst case | Extra space | Stable |
|---|---|---|---|---|
| O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
The splits do not look at the values, so the same merges happen for every input of a given size. Only the number of comparisons changes: a merge stops comparing as soon as one side runs out. Run Already sorted and Random at the same size and compare the counters.
The write counter includes the copies into the temporary arrays, so every value in a merge is written twice. That copy is where the O(n) of extra space comes from.
The C# code
The listing beside the bars is the SortArray() and MergeArray() methods from Merge Sort in C#. The article explains the code and measures it with BenchmarkDotNet.
FAQ
Is merge sort stable?
Yes. When the two front values are equal, this code takes the one from the left half first, so equal values keep their order.
Why does merge sort need extra memory?
Merging in place would overwrite values that are still needed. This code copies both halves into temporary arrays first, and for the last merge they hold as many values as the whole array.
Is merge sort faster than quicksort?
It depends on the data. Merge sort makes fewer comparisons and never drops to O(n²), but it copies every value at each level. Quicksort sorts in place and is often faster on arrays in memory when its pivots are chosen well.