AlgoViz
HomeSorting Techniques

Merge Sort

Medium

Divide, sort halves, merge

In simple words

Split the list in half again and again, then gently zip the sorted halves back together in order.

The idea

Split the array in half, recursively sort each half, then merge the two sorted runs by repeatedly taking the smaller front element. Guaranteed O(n log n) and stable.

The trick

  • The merge step is the heart: two sorted runs combine in linear time.
6
3
8
5
2
7
4
1
0
1
2
3
4
5
6
7

Step 1 of 33. Split the array down to single elements, then merge the sorted halves back together. Values: 6, 3, 8, 5, 2, 7, 4, 1.

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.