Merge Sorting

Medium

Split in half, sort each, zip together

Problem

Sort the array using merge sort: split in half, sort each half, then merge the two sorted halves.

In simple words

Split the list in half, sort each half, then zip the two sorted halves together.

The idea

Recursively halve the array until each piece is one element (trivially sorted), then merge pairs of sorted pieces by repeatedly taking the smaller front element. The halving gives log n levels and each level merges n elements, so the total is a guaranteed O(n log n) regardless of input.

The trick

O(n log n) always — no bad input, unlike quick sort.
Needs O(n) extra space for the merge buffer.
Stable, which is why it underpins sorting of objects by multiple keys.

←→stepspaceplay

1/33

Optimal

timeO(n log n)spaceO(n)

Stable, predictable.

1// split, sort each half, then merge the sorted runs2function sort(lo, hi) {3  if (lo >= hi) return;4  const mid = (lo + hi) >> 1;5  sort(lo, mid); sort(mid + 1, hi);6  merge(lo, mid, hi);7}8function merge(lo, mid, hi) {9  while (i <= mid && j <= hi)10    if (a[i] <= a[j]) out.push(a[i++]);11    else out.push(a[j++]);12  while (i <= mid) out.push(a[i++]);13  while (j <= hi) out.push(a[j++]);14}

Input

array: [6, 3, 8, 5, 2, 7, 4, 1]

Memory

write: —

Output

result: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: nums = [38, 27, 43, 3, 9, 82, 10]
Output:: [3, 9, 10, 27, 38, 43, 82]
Explanation:: Split, sort halves, merge.

Example 2

Input:: nums = [5, 2, 4, 1]
Output:: [1, 2, 4, 5]
Explanation:: Halves [5,2] and [4,1] merge in order.

Example 3

Input:: nums = [1]
Output:: [1]
Explanation:: A single element is already sorted.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.