DSA for Interviews, From Zero

Part 3 · Lesson 17 · 24 min read

Merge Sort

Split, sort the halves, merge — divide and conquer.

On this page

  1. Divide and conquer
  2. Merging two sorted arrays
  3. Traced: merge([1, 4, 7], [2, 3, 9])
  4. Merge sort: split, sort, merge
  5. The recursion tree
  6. Why it is O(n log n)
  7. Extra space and stability
  8. Counting inversions (a preview)
  9. Practice questions (6)
  10. Make it stick
  11. What's next

Divide and conquer

Sorting 1,000 cards is hard. Sorting two piles of 500 is easier, and sorting a pile of one card needs no work at all. Divide and conquer is a method of solving a problem that uses this idea. It splits the problem into smaller copies of itself, solves each copy (by recursion, Lesson 14), and then combines the answers. Merge sort is a sorting algorithm that uses divide and conquer.

For sorting, that becomes three steps:

  1. Divide: cut the array into two halves.
  2. Conquer: sort each half, using recursion (the same method again).
  3. Combine: merge the two sorted halves into one sorted array.

Steps 1 and 2 are very short to write. All the real work is in step 3, so we learn it first.

Merging two sorted arrays

Merging means joining two arrays that are already sorted into one sorted array. Put a finger at the start of each array. The smaller of the two front items is the smallest item overall, so take it and move that finger forward. Repeat until one array runs out. Then copy the rest of the other array.

Traced: merge([1, 4, 7], [2, 3, 9])

step 1 / 21
Set up
merge([1, 4, 7], [2, 3, 9])

Both inputs are already sorted. That is the whole idea.

▶function merge(a, b) {2  const out = [];3  let i = 0, j = 0;4  while (i < a.length && j < b.length) {5    if (a[i] <= b[j]) out.push(a[i++]);6    else out.push(b[j++]);7  }8  while (i < a.length) out.push(a[i++]);9  while (j < b.length) out.push(b[j++]);10  return out;11}12console.log(merge([1, 4, 7], [2, 3, 9]));
Variables
a[1, 4, 7]
b[2, 3, 9]
Console
(nothing printed yet)
Each comparison places exactly one item. Nothing is ever compared twice. · interactive

Every step places one item in out, so merging arrays of lengths n and m takes O(n + m) time. This two-finger walk is also the start of the two-pointer pattern (using two indexes that move through the data), which you will meet in Lesson 21.

Merge sort: split, sort, merge

JavaScript
function merge(a, b) {  const out = [];  let i = 0, j = 0;  while (i < a.length && j < b.length) {    if (a[i] <= b[j]) out.push(a[i++]);    else out.push(b[j++]);  }  while (i < a.length) out.push(a[i++]);  while (j < b.length) out.push(b[j++]);  return out;}function mergeSort(arr) {  if (arr.length <= 1) return arr;                  // base case: already sorted  const mid = Math.floor(arr.length / 2);  const left = mergeSort(arr.slice(0, mid));        // sort the left half  const right = mergeSort(arr.slice(mid));          // sort the right half  return merge(left, right);                        // combine}console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));// [ 3, 9, 10, 27, 38, 43, 82 ]

Read mergeSort using the recursion rule from Lesson 14. Trust that the two recursive calls return sorted halves. Then merge combines them. The base case is an array of 0 or 1 items, because such an array is already sorted.

The recursion tree

A recursion tree is a picture of all the recursive calls, with the biggest call at the top. Here is every call for [38, 27, 43, 3, 9, 82, 10], one level per row:

Dry run · splitting down, then merging back up
LevelPieces
0 (split)[38, 27, 43, 3, 9, 82, 10]
1 (split)[38, 27, 43] · [3, 9, 82, 10]
2 (split)[38] · [27, 43] · [3, 9] · [82, 10]
3 (base cases)[38] · [27] · [43] · [3] · [9] · [82] · [10]
2 (merged)[38] · [27, 43] · [3, 9] · [10, 82]
1 (merged)[27, 38, 43] · [3, 9, 10, 82]
0 (merged)[3, 9, 10, 27, 38, 43, 82]

On the way down nothing is sorted. The array is only cut into pieces. All the sorting happens in the merges on the way back up.

Why it is O(n log n)

Look at the tree level by level:

  • Work per level: the merges on one level together touch every item once, because the pieces on a level add up to the whole array. So each level costs O(n).
  • Number of levels: each level halves the piece size, from n down to 1. This is the halving loop from Lesson 12. It gives about log₂ n levels (log₂ n is how many times you can halve n before you reach 1).

n work on each of log n levels gives O(n log n). This is true in the best, average and worst case, because merge sort always splits the array in the same way, whatever the values are. For n = 1,000,000 that is about 20 million steps. An O(n²) sort needs about 1012.

Dry run · cost of merge sort on n = 8
LevelPiecesPiece sizeWork on this level
1248
2428
3818

3 levels (log₂ 8) × 8 items = 24 steps of merging.

Extra space and stability

Merge sort is not in place (Lesson 16 explained in-place sorts). merge builds a new array, so merge sort needs O(n) extra space, plus O(log n) for the recursion depth. This is its main disadvantage compared with quick sort (Lesson 18).

It is stable (equal items keep their original order), thanks to one character: a[i] <= b[j]. When the two front items are equal, the item from the left half is taken first, because it came first in the original array. If you wrote < instead, the array would still be sorted correctly, but the sort would no longer be stable.

Where you meet merge sort in practice

JavaScript's sort uses TimSort. TimSort is a mix of merge sort and insertion sort. It first finds parts of the data that are already sorted (called runs) and then merges them. Merge sort is also the standard way to sort a linked list (Lesson 37). This is because merging needs no random access (jumping straight to the item at any index).

Counting inversions (a preview)

Lesson 16 counted inversions (pairs i < j with arr[i] > arr[j]) in O(n²). Merge sort can count them with almost no extra work. During a merge, suppose an item from the right half is taken. It is smaller than every item still waiting in the left half. And each of those left items came before it in the original array. So that one step finds left.length - i inversions at once.

JavaScript
function countInversions(arr) {  let count = 0;  function sort(a) {    if (a.length <= 1) return a;    const mid = Math.floor(a.length / 2);    const left = sort(a.slice(0, mid));    const right = sort(a.slice(mid));    const out = [];    let i = 0, j = 0;    while (i < left.length && j < right.length) {      if (left[i] <= right[j]) out.push(left[i++]);      else {        count += left.length - i;     // right[j] is smaller than every remaining left item        out.push(right[j++]);      }    }    while (i < left.length) out.push(left[i++]);    while (j < right.length) out.push(right[j++]);    return out;  }  sort(arr);  return count;}console.log(countInversions([5, 3, 8, 1, 4])); // 6console.log(countInversions([1, 2, 3]));       // 0

This has the same O(n log n) time as merge sort. Changing the “combine” step so that it also collects extra information is a common divide-and-conquer technique.

Practice questions

Most of these use only the merge step. In interviews, it is more useful than the full sort.

Q1Merge sorted array (in place)Easy

nums1 has length m + n. Its first m values are sorted, and the rest are zeros. Merge the sorted nums2 (length n) into nums1 so that nums1 is sorted. Change nums1 itself; do not return a new array.

Example 1
Input: nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
Output: [1, 2, 2, 3, 5, 6]
Explanation: The last n slots of nums1 are empty space (filled with zeros) where the merged values will go.
Example 2
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: Edge case: nums1 has no real values.
Stuck? Open one hint at a time
Hint 1
If you merge from the front, you would overwrite values of nums1 that you still need.
Hint 2
The empty space is at the end. So merge from the back. Place the largest remaining value at the last free position.
Show all 2 solutions with explanations
Approach 1Merge into a new array, copy back
The idea

Do the normal merge into a temporary array. Then copy the result into nums1.

JavaScript
function merge(nums1, m, nums2, n) {  const out = [];  let i = 0, j = 0;  while (i < m && j < n) out.push(nums1[i] <= nums2[j] ? nums1[i++] : nums2[j++]);  while (i < m) out.push(nums1[i++]);  while (j < n) out.push(nums2[j++]);  for (let k = 0; k < m + n; k++) nums1[k] = out[k];}const a = [1, 2, 3, 0, 0, 0];merge(a, 3, [2, 5, 6], 3);console.log(a); // [ 1, 2, 2, 3, 5, 6 ]
How it works

O(m + n) time, O(m + n) extra space.

Approach 2Merge from the back
The idea

Keep three positions: the last real value of nums1 (i), the last value of nums2 (j), and the last slot to fill (k). Place the larger of the two values at k, and move left.

JavaScript
function merge(nums1, m, nums2, n) {  let i = m - 1, j = n - 1, k = m + n - 1;  while (j >= 0) {                          // until every nums2 value is placed    if (i >= 0 && nums1[i] > nums2[j]) nums1[k--] = nums1[i--];    else nums1[k--] = nums2[j--];  }}const a = [1, 2, 3, 0, 0, 0];merge(a, 3, [2, 5, 6], 3);console.log(a); // [ 1, 2, 2, 3, 5, 6 ]const b = [0];merge(b, 0, [1], 1);console.log(b); // [ 1 ]
How it works
Dry run · nums1 = [1, 2, 3, _, _, _], nums2 = [2, 5, 6]
ComparePlace at knums1 after
3 vs 66 at 5[1, 2, 3, _, _, 6]
3 vs 55 at 4[1, 2, 3, _, 5, 6]
3 vs 23 at 3[1, 2, 3, 3, 5, 6]
2 vs 22 (nums2) at 2[1, 2, 2, 3, 5, 6]

Once nums2 is used up, the remaining nums1 values are already in the right place. The writing position k never goes below i, so no value is overwritten too early.

Which approach should you use?

Merging from the back is the expected answer. It takes O(m + n) time and O(1) extra space. “Fill from the end when the free space is at the end” is a useful trick to remember. (LeetCode 88.)

Q2Squares of a sorted arrayEasy

Given an array sorted in non-decreasing order (each value is equal to or bigger than the one before), return the squares of its values, also sorted.

Example 1
Input: [-4, -1, 0, 3, 10]
Output: [0, 1, 9, 16, 100]
Explanation: The squares are 16, 1, 0, 9, 100; sorted gives this.
Example 2
Input: [-7, -3, 2, 3, 11]
Output: [4, 9, 9, 49, 121]
Explanation: Negative numbers can have large squares.
Stuck? Open one hint at a time
Hint 1
Squaring and then sorting is O(n log n). Can you use the fact that the input is already sorted?
Hint 2
The largest square comes from one of the two ends of the array. Fill the result from the back.
Show all 2 solutions with explanations
Approach 1Square, then sort
The idea

The simple way: square every value, then sort.

JavaScript
function sortedSquares(nums) {  return nums.map((x) => x * x).sort((a, b) => a - b);}console.log(sortedSquares([-4, -1, 0, 3, 10])); // [ 0, 1, 9, 16, 100 ]
How it works

O(n log n).

Approach 2Merge from both ends
The idea

The squares of the negative part get smaller as you move right. The squares of the positive part get bigger as you move right. That gives two sorted sequences. Merge them, taking the largest first.

JavaScript
function sortedSquares(nums) {  const out = new Array(nums.length);  let left = 0, right = nums.length - 1;  for (let k = nums.length - 1; k >= 0; k--) {    const a = nums[left] * nums[left];    const b = nums[right] * nums[right];    if (a > b) { out[k] = a; left++; }    else { out[k] = b; right--; }  }  return out;}console.log(sortedSquares([-4, -1, 0, 3, 10])); // [ 0, 1, 9, 16, 100 ]console.log(sortedSquares([-7, -3, 2, 3, 11])); // [ 4, 9, 9, 49, 121 ]
How it works

O(n), because each step places one value. It is the merge step from this lesson, reading two sorted sequences from their large ends.

Which approach should you use?

Approach 2 is the answer that interviewers expect as a follow-up. The key step is to see “two sorted sequences hidden in one array”. (LeetCode 977.)

Q3Sort an array with merge sortMedium

Sort nums in ascending order (smallest first) without the built-in sort, in O(n log n) time.

Example 1
Input: [5, 1, 1, 2, 0, 0]
Output: [0, 0, 1, 1, 2, 5]
Explanation: There can be up to 5 × 10⁴ values, so an O(n log n) sort is needed.
Stuck? Open one hint at a time
Hint 1
Write merge, then mergeSort with a base case of length ≤ 1.
Hint 2
To avoid creating many small arrays, you can sort ranges of indexes in one array and use one shared temporary array (a buffer).
Show all 2 solutions with explanations
Approach 1Merge sort with slices
The idea

Use the version from the lesson.

JavaScript
function sortArray(nums) {  if (nums.length <= 1) return nums;  const mid = Math.floor(nums.length / 2);  const a = sortArray(nums.slice(0, mid));  const b = sortArray(nums.slice(mid));  const out = [];  let i = 0, j = 0;  while (i < a.length && j < b.length) out.push(a[i] <= b[j] ? a[i++] : b[j++]);  while (i < a.length) out.push(a[i++]);  while (j < b.length) out.push(b[j++]);  return out;}console.log(sortArray([5, 1, 1, 2, 0, 0])); // [ 0, 0, 1, 1, 2, 5 ]
How it works

O(n log n) time. It is simple, but it creates many small arrays that are thrown away soon after.

Approach 2Merge sort on index ranges
The idea

Sort nums[lo..hi] in place, and use one shared temporary buffer for every merge.

JavaScript
function sortArray(nums) {  const buf = new Array(nums.length);  function sort(lo, hi) {                   // sorts nums[lo..hi]    if (lo >= hi) return;    const mid = Math.floor((lo + hi) / 2);    sort(lo, mid);    sort(mid + 1, hi);    let i = lo, j = mid + 1, k = lo;    while (i <= mid && j <= hi) buf[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];    while (i <= mid) buf[k++] = nums[i++];    while (j <= hi) buf[k++] = nums[j++];    for (let t = lo; t <= hi; t++) nums[t] = buf[t];  }  sort(0, nums.length - 1);  return nums;}console.log(sortArray([5, 1, 1, 2, 0, 0]));       // [ 0, 0, 1, 1, 2, 5 ]console.log(sortArray([38, 27, 43, 3, 9, 82, 10])); // [ 3, 9, 10, 27, 38, 43, 82 ]
How it works

The time is the same, O(n log n), and the space is O(n). But only one extra array is ever created. Working on index ranges (lo, hi) instead of copies is the style that quick sort uses too.

Which approach should you use?

Either one passes. Version 2 is closer to what a library does, and it avoids the cost of slice. (LeetCode 912.)

Q4Intersection of two sorted arraysEasy

Given two sorted arrays, return their common values in sorted order. A value that appears twice in both arrays appears twice in the answer.

Example 1
Input: [1, 2, 2, 3, 5], [2, 2, 4, 5]
Output: [2, 2, 5]
Explanation: Keep each common value as many times as it appears in both.
Example 2
Input: [1, 3], [2, 4]
Output: []
Explanation: No common values.
Stuck? Open one hint at a time
Hint 1
Both arrays are sorted. Walk through them together, as in a merge.
Hint 2
If the values are equal, record the value and move both fingers. Otherwise move the finger on the smaller value.
Show the solution with explanations
Approach 1Merge-style walk
The idea

Use two fingers. If the values are equal, take the value and move both fingers. Otherwise move the finger on the smaller value, because that value cannot match anything later.

JavaScript
function intersectSorted(a, b) {  const out = [];  let i = 0, j = 0;  while (i < a.length && j < b.length) {    if (a[i] === b[j]) { out.push(a[i]); i++; j++; }    else if (a[i] < b[j]) i++;    else j++;  }  return out;}console.log(intersectSorted([1, 2, 2, 3, 5], [2, 2, 4, 5])); // [ 2, 2, 5 ]console.log(intersectSorted([1, 3], [2, 4]));                // []
How it works

O(n + m) time, and O(1) extra space apart from the output. No Set is needed, because the inputs are sorted.

Which approach should you use?

Compare this with Lesson 12, where unsorted input needed a Set. Sorted input often removes the need for extra memory. (Related: LeetCode 350.)

Q5Count inversions fastHard

Return the number of pairs i < j with nums[i] > nums[j], for up to 105 values.

Example 1
Input: [2, 4, 1, 3, 5]
Output: 3
Explanation: (2, 1), (4, 1), (4, 3).
Example 2
Input: [5, 4, 3, 2, 1]
Output: 10
Explanation: Every pair is inverted: 5 × 4 / 2 = 10.
Stuck? Open one hint at a time
Hint 1
Counting every pair is O(n²), which is too slow for 105 values.
Hint 2
During a merge, when you take an item from the right half, how many left-half items are bigger than it?
Show the solution with explanations
Approach 1Merge sort that counts
The idea

Every time the merge step places a right-half item before the remaining left-half items, it adds left.length - i to the count.

JavaScript
function countInversions(nums) {  let count = 0;  function sort(a) {    if (a.length <= 1) return a;    const mid = Math.floor(a.length / 2);    const l = sort(a.slice(0, mid)), r = sort(a.slice(mid));    const out = [];    let i = 0, j = 0;    while (i < l.length && j < r.length) {      if (l[i] <= r[j]) out.push(l[i++]);      else { count += l.length - i; out.push(r[j++]); }    }    return out.concat(l.slice(i), r.slice(j));  }  sort(nums);  return count;}console.log(countInversions([2, 4, 1, 3, 5])); // 3console.log(countInversions([5, 4, 3, 2, 1])); // 10
How it works
Dry run · the final merge of [2, 4] and [1, 3, 5]
TakeFromInversions added
1right2 (both 2 and 4 are bigger)
2left0
3right1 (only 4 is left and bigger)
4left0
5right0 (left is empty)

Earlier merges found none, so the total is 2 + 1 = 3.

Which approach should you use?

O(n log n) instead of O(n²). The inversion count measures “how unsorted” an array is. For example, it can show how different two people's rankings are.

Q6Merge k sorted arraysMedium

Given k sorted arrays, merge them into one sorted array.

Example 1
Input: [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]
Explanation: All values, in sorted order.
Stuck? Open one hint at a time
Hint 1
If you merge the arrays one by one into a growing result, you copy the same values again and again.
Hint 2
Merge them in pairs, like the levels of merge sort. The number of arrays goes k → k/2 → k/4 … → 1.
Show all 2 solutions with explanations
Approach 1Merge one by one
The idea

Start with the first array. Then merge each next array into the result.

JavaScript
function merge(a, b) {  const out = [];  let i = 0, j = 0;  while (i < a.length && j < b.length) out.push(a[i] <= b[j] ? a[i++] : b[j++]);  return out.concat(a.slice(i), b.slice(j));}function mergeK(lists) {  let result = [];  for (const list of lists) result = merge(result, list);  return result;}console.log(mergeK([[1, 4, 5], [1, 3, 4], [2, 6]])); // [ 1, 1, 2, 3, 4, 4, 5, 6 ]
How it works

With N values in total, the growing result is copied up to k times. So the time is O(N × k).

Approach 2Merge in pairs (divide and conquer)
The idea

Merge arrays 0 and 1, then 2 and 3, and so on. Then merge those results in pairs again, until one array remains.

JavaScript
function merge(a, b) {  const out = [];  let i = 0, j = 0;  while (i < a.length && j < b.length) out.push(a[i] <= b[j] ? a[i++] : b[j++]);  return out.concat(a.slice(i), b.slice(j));}function mergeK(lists) {  if (lists.length === 0) return [];  while (lists.length > 1) {    const next = [];    for (let i = 0; i < lists.length; i += 2) {      next.push(i + 1 < lists.length ? merge(lists[i], lists[i + 1]) : lists[i]);    }    lists = next;  }  return lists[0];}console.log(mergeK([[1, 4, 5], [1, 3, 4], [2, 6]])); // [ 1, 1, 2, 3, 4, 4, 5, 6 ]console.log(mergeK([]));                             // []
How it works

Each round touches every value once, which is O(N). The number of lists halves each round, so there are log k rounds. The total is O(N log k). This is the same reasoning as merge sort's O(n log n).

Which approach should you use?

Pairwise merging is the divide-and-conquer answer. Lesson 46 solves the same problem with a heap (a structure that always gives you the smallest item quickly), also in O(N log k). (Related: LeetCode 23, which uses linked lists.)

Make it stick

Make it stick — close this page, then
  1. Write merge from memory, including the two “leftover” loops.
  2. Draw the recursion tree for merge sort on [4, 1, 3, 2].
  3. Explain O(n log n) using “work per level” and “number of levels”.
  4. Say which single character makes merge sort stable.

Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.

What's next

Merge sort does its work while combining. Quick sort does the opposite. It does its work while splitting, and it needs no merge at all. Lesson 18 covers quick sort and quickselect. It also shows how to use JavaScript's sort correctly, including its well-known trap with numbers.

Practise on LeetCode

Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.

Published by Jainik · Last updated · How these lessons are made

Keep learning

Related series