Step 2 of 6

Merge sort

Merge sort splits the array in half, sorts each half recursively, then merges the two sorted halves by repeatedly taking the smaller front element.

• Always O(n log n), even in the worst case.
• Stable, which is why std::stable_sort is usually a merge sort.
• Needs O(n) extra memory for merging.

The merge step is the heart of it (you wrote one for strings in the STL module). Your turn: implement merge_sort(std::vector<int>& v). The test sorts 200,000 numbers, so an O(n²) sort won't finish in time.

Previous: Insertion sort Next: Quicksort and partitioning