Algorithms from zero

Merge sort

Crux Merge sort divides the array, recursively sorts each half, then merges them in O(n) time. The result: O(n log n) always. It is stable and not in-place, using O(n) extra memory. First taste of divide and conquer.

◷ 21 min

You have seen simple sorts: selection, insertion, bubble. All run in O(n²) and are too slow for large data. Fast algorithms (merge sort, quicksort) use a clever trick: divide the array into pieces, solve each piece independently, then combine the solutions. This is divide and conquer. Merge sort is the purest example. It splits the array in half, recursively sorts each half, then merges the two sorted halves back together in linear time. The result is O(n log n)—always, even in the worst case.

Goal

After this lesson you understand merge sort: how to merge two already-sorted arrays in O(n) time, how the divide-and-conquer strategy works, why merge sort is always O(n log n) (log n levels of splitting, O(n) merging per level), why it is stable (equal elements stay in order) and not in-place (uses O(n) extra memory), and what divide and conquer means as a general algorithm pattern.

The idea

Divide and conquer: the strategy

The core idea behind merge sort is this: if you can split a problem into two independent subproblems of half the size, solve each recursively, and then combine their solutions, you often get a much faster algorithm.

Merge sort follows three steps:

Divide: Split the array in half (or stop if it has one element).
Conquer: Recursively call merge sort on each half.
Combine: Merge the two sorted halves back together into one sorted array.

The merge step: combining two sorted arrays

The heart of merge sort is the merge function. Given two already-sorted arrays, merge them into one sorted array in O(n) time using two pointers.

Imagine two sorted arrays side by side:

Left: [1, 3, 5]
Right: [2, 4, 6]

Start with two pointers, one at the front of each array. Compare the elements at both pointers. Take the smaller one, move the pointer of that array forward, and repeat:

Left: [1, 3, 5]
       ^
Right: [2, 4, 6]
       ^
Compare: 1 < 2. Take 1. Left pointer moves right.

Left: [1, 3, 5]
          ^
Right: [2, 4, 6]
       ^
Compare: 3 > 2. Take 2. Right pointer moves right.

Left: [1, 3, 5]
          ^
Right: [2, 4, 6]
          ^
Compare: 3 < 4. Take 3. Left pointer moves right.

(continue...)
Result: [1, 2, 3, 4, 5, 6]

Why O(n)? You walk each pointer through its array exactly once. Total steps = left.length + right.length = O(n).

Why merge sort is O(n log n)

The time complexity comes from two things: how many levels of splitting, and how much work at each level.

How many levels of splitting? The array is halved each time: n → n/2 → n/4 → … → 1. That is log n levels.

From the math track Logarithms

How much work per level? At each level, you merge subarrays. The total work across all subarrays at one level is O(n)—you touch each element once.

Level 1 (full array): merge one time, O(n) work.
Level 2 (two halves): merge two times, O(n/2) + O(n/2) = O(n) work.
Level 3 (four quarters): merge four times, O(n/4) × 4 = O(n) work.
…
Level log n: many small merges, still O(n) total work.

Total: log n levels × O(n) work per level = O(n log n).

Stability and space

Merge sort is stable: when merging, if both pointers point to equal elements, you take from the left array first. This preserves the original order of equal elements.

Merge sort is not in-place: you create a new array during the merge step to hold the merged result. This costs O(n) extra space. A recursive merge sort also uses O(log n) space for the call stack. Total: O(n).

The code

Let us code merge sort from the ground up.

Step 1: Merge two sorted arrays

function merge(left, right) {
  const result = [];
  let i = 0;  // Pointer into left
  let j = 0;  // Pointer into right

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  // If left still has elements, append them
  while (i < left.length) {
    result.push(left[i]);
    i++;
  }

  // If right still has elements, append them
  while (j < right.length) {
    result.push(right[j]);
    j++;
  }

  return result;
}

Note: left[i] <= right[j] (not <) preserves stability. If elements are equal, take from the left array first.

Step 2: Merge sort recursively

function mergeSort(arr) {
  // Base case: array of length 0 or 1 is already sorted
  if (arr.length <= 1) {
    return arr;
  }

  // Divide: find the midpoint
  const mid = Math.floor(arr.length / 2);

  // Conquer: recursively sort each half
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  // Combine: merge the sorted halves
  return merge(left, right);
}

This is the full algorithm. The recursion terminates when the array has 0 or 1 elements (already sorted).

Let us run it:

function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}

const unsorted = [38, 27, 43, 3, 9, 82, 10];
const sorted = mergeSort(unsorted);
console.log("Original:", unsorted);
console.log("Sorted:  ", sorted);

// Test stability
const items = [
{ val: 3, id: 'a' },
{ val: 1, id: 'b' },
{ val: 3, id: 'c' },
{ val: 2, id: 'd' }
];

function mergeSortStable(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSortStable(arr.slice(0, mid));
const right = mergeSortStable(arr.slice(mid));
return mergeStable(left, right);
}

const sorted2 = mergeSortStable(items);
console.log("Stable sort (equal 3's stay in order a, then c):");
sorted2.forEach(x => console.log(`  val=${x.val}, id=${x.id}`));

Output

Step-by-step trace

Let us trace merge sort on a small array: [38, 27, 43, 3].


      1
      function mergeSort(arr) {
    

      2
        if (arr.length <= 1) return arr;
    

      3
        const mid = Math.floor(arr.length / 2);
    

      4
        const left = mergeSort(arr.slice(0, mid));
    

      5
        const right = mergeSort(arr.slice(mid));
    

      6
        return merge(left, right);
    

      7
      }

Complexity

Aspect	Value
Time (best case)	O(n log n)
Time (average case)	O(n log n)
Time (worst case)	O(n log n)
Space	O(n)
Stable?	Yes
In-place?	No

Why always O(n log n)?

Unlike selection sort (always O(n²)) or insertion sort (O(n) best, O(n²) worst), merge sort does not change based on the input order. It always divides the array into halves log n times, and each level of merging costs O(n). The result is always O(n log n)—no best case, no worst case, just O(n log n).

Stability:

Merge sort preserves the order of equal elements. When merging and both pointers point to equal values, take from the left array first. This guarantees stability.

Space:

Merge sort uses O(n) extra space to create temporary arrays during the merge step. If the input array has n elements, you allocate roughly n elements of temporary space. Recursion adds O(log n) on the call stack (depth of recursion = log n). Total: O(n).

This is the tradeoff: merge sort is fast and predictable, but uses extra memory.

Practice 0 / 5

Why is merge sort O(n log n) even when the input is already sorted?

When merging two sorted arrays, why do we use two pointers instead of searching for each element?

Merge sort uses O(n) extra space. Why is this worse than selection sort (O(1))?

Is merge sort stable? That is, do equal elements keep their original order?

How many levels of splitting happen when you merge sort an array of 16 elements?

lesson.inset.advantage

When to use merge sort. Merge sort is O(n log n) always, making it predictable and fast for large data. It is stable, so it preserves order (useful when sorting by multiple keys). Real databases and systems often use merge sort or its variants. Downside: it uses O(n) extra space. Use it when speed is critical and memory is available. For very large datasets, prefer in-place algorithms like quicksort (though quicksort is not stable).

lesson.inset.pattern

Divide and conquer as a strategy. Merge sort is the first divide-and-conquer algorithm you see. The pattern: split the problem into independent subproblems, solve each recursively, combine the solutions. This works for many problems: searching a balanced tree, multiplying large numbers, finding the closest pair of points. The key: the subproblems must be independent (solving one does not affect the other), and combining must be efficient.

Check yourself

Quiz

You need to sort a million-element array and you have 2 GB of RAM. The array is 800 MB. Which is the better choice: merge sort (needs 800 MB extra) or selection sort (needs O(1) extra)?

Recap

Merge sort divides the array in half, recursively sorts each half, then merges them together.

The merge step takes two sorted arrays and combines them in O(n) time using two pointers: walk both arrays, compare at each step, take the smaller element.

Time complexity: O(n log n) always (log n levels of splitting, O(n) work per level). Never O(n²), even on bad input.

Space: O(n) for temporary arrays during merging.

Stable: Yes. Equal elements keep their original order.

In-place: No. Needs O(n) extra memory.

Divide and conquer: The key insight—split the problem in half, solve each half independently, combine. Fast and powerful. This pattern works for many algorithms beyond sorting.

Why learn it? Merge sort teaches you divide and conquer, one of the most important algorithm design strategies. It also shows O(n log n), a complexity class you will see in many real systems.

Continue the climb ↑Quicksort