Understanding Merge Sort by Following the Recursion

Introduction

Merge sort does two simple jobs repeatedly: split a large array into smaller pieces, then merge sorted pieces back together.

Merge sort became easier for me to understand when I stopped trying to picture the whole algorithm happening at once. It performs two different jobs:

1. Splitting: keep reducing an array into smaller subproblems.
2. Merging: combine two already-sorted subarrays into a larger sorted array.

The recursive calls handle the splitting. The ordering work happens while those calls return.

This article treats merge sort as a learning exercise from The Odin Project. There is no accessible dedicated repository for the author's exercise, so the examples below demonstrate the algorithm without claiming to reproduce that earlier implementation.

The divide-and-conquer idea

Merge sort is a divide-and-conquer algorithm:

• Divide the input into two smaller arrays.
• Conquer each half by sorting it recursively.
• Combine the two sorted results with a merge operation.

The important condition during the combine step is that both inputs to merge are already sorted. Merging [3, 8] and [1, 5] is a smaller problem than sorting [8, 3, 5, 1] from the beginning because the algorithm only needs to compare the first unused value from each half.

Start with the base case

Every recursive solution needs a condition that stops further calls. For merge sort, an array with zero or one element is already sorted:

if the array length is 0 or 1:
    return the array

Using length <= 1 handles both an empty array and a one-element array. Without that base case, splitting an empty or one-element array would never make useful progress.

The recursive case must then create strictly smaller problems. Dividing an array around its middle provides that progress:

middle = floor(length / 2)
left  = mergeSort(first half)
right = mergeSort(second half)
return merge(left, right)

Each call receives about half as many elements as its parent, so the recursion eventually reaches the base case.

Follow one array all the way down and back up

Consider this input:

[8, 3, 5, 1]

The complete flow is shown below. The upper arrows split the problem; the lower arrows show sorted results being merged.

The calls unfold in this order:

1. mergeSort([8, 3, 5, 1]) calls mergeSort([8, 3]) for its left half.
2. That call invokes mergeSort([8]), which reaches the base case and returns [8].
3. It then invokes mergeSort([3]), which returns [3].
4. The waiting left-half call evaluates merge([8], [3]) and returns [3, 8].
5. The original call moves to its right half and invokes mergeSort([5, 1]).
6. Its child calls return [5] and [1] from their base cases.
7. The right-half call evaluates merge([5], [1]) and returns [1, 5].
8. The original call finally evaluates merge([3, 8], [1, 5]) and returns [1, 3, 5, 8].

Notice what does not happen: the first split does not somehow sort [8, 3] immediately. That call has to split again. Only after [8] and [3] return from their base cases can they be merged as [3, 8].

This is the recursion's return journey:

1. [8] returns because it is a base case.
2. [3] returns for the same reason.
3. Their waiting parent call merges them into [3, 8].
4. The right side independently produces [1, 5].
5. The original call can finally merge the two sorted halves.

The call stack remembers which parent calls are waiting. Recursion does not remove the need to track that unfinished work; the runtime holds it in stack frames until the smaller calls return.

The final merge, one comparison at a time

At the top level, the algorithm has these sorted inputs:

left  = [3, 8]
right = [1, 5]

Use one cursor for each input and compare only the values at those cursors:

Why is it safe to take the smaller candidate? Because each half is sorted. If 3 is the first remaining value on the left, nothing later in that half can be smaller than 3. The same rule applies to the right half. This rule is sometimes called an invariant. An invariant is a condition that should remain true while an operation is running. Here, the remaining part of each input stays sorted throughout the merge.

Once one side is exhausted, all remaining values on the other side can be appended in their existing order.

A focused JavaScript implementation

The reasoning comes first; the code now follows it directly:

function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

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

  return result.concat(
    left.slice(leftIndex),
    right.slice(rightIndex),
  );
}

function mergeSort(values) {
  if (values.length <= 1) {
    return values.slice();
  }

  const middle = Math.floor(values.length / 2);
  const left = mergeSort(values.slice(0, middle));
  const right = mergeSort(values.slice(middle));

  return merge(left, right);
}

console.log(mergeSort([8, 3, 5, 1]));
// [1, 3, 5, 8]

This is a demonstration implementation, not a recovered version of the author's original exercise.

Several lines express important invariants:

• values.length <= 1 is the stopping condition.
• Both recursive calls receive smaller arrays.
• merge is called only after both halves have returned in sorted order.
• The loop advances exactly one cursor on every iteration.
• The comparison uses <=, so equal values from the left half are kept before equal values from the right half.
• The function returns new arrays instead of rearranging the input array in place.

The cursor variables matter. They let the algorithm move forward through each array without removing values from its front.

Why merge sort is usually written as O(n log n)

The notation can look more complicated than the idea it represents. In this section, n means the number of values in the input. The notation describes how the amount of work grows when the input becomes larger; it is not an exact time measurement in seconds.

For example, imagine an array with eight values. Merge sort keeps dividing it into smaller groups:

8 values → 4 values → 2 values → 1 value

After reaching single-value arrays, it merges the groups again. At each level, the algorithm processes all of the values once while merging. The number of levels grows slowly because the input is divided by two each time. This combination of processing n values across approximately log n levels is written as O(n log n).

The O notation is called Big O notation. It is a shorthand for describing an upper limit on how an algorithm's work grows. It does not tell us the exact running time because array copying, memory allocation, the JavaScript engine, the input values, and the computer being used also affect the result.

Standard merge sort has the same general growth in its best, average, and worst cases because it continues to split and merge even when the input is already partly sorted.

Extra memory and array slicing

The merge step needs temporary space for its result. A typical array version therefore uses additional memory that grows with the input size, along with memory for the unfinished recursive calls. The recursive calls form a stack: each call waits for its smaller calls to finish before it can merge their results. The stack becomes deeper as the input is repeatedly divided, but it does not grow as quickly as the temporary arrays.

This is often summarised as Θ(n) additional array space and Θ(log n) recursion-stack space. The symbols are only a compact way to describe the growth. The practical meaning is that merge sort needs extra arrays, and it also keeps a smaller number of waiting function calls in memory.

The example also calls slice() when splitting and when appending leftovers. Those calls copy array elements and allocate arrays. Across the entire run they create more temporary allocations than an index-range implementation that shares one input array and one reusable buffer. Under ordinary sequential evaluation, the peak live array storage remains linear in n, but the cumulative amount allocated and copied can be larger and may create more garbage-collection work.

An index-range version passes boundaries such as start, middle, and end instead of creating a new subarray for every recursive call. That is often a useful refinement after the recursive model is understood; it is not necessary for learning why the algorithm works.

Stability depends on the merge rule

A sorting algorithm is stable when records with equal sort keys keep their original relative order. Suppose these objects are sorted by score:

[
  { name: "A", score: 5 },
  { name: "B", score: 5 },
]

A stable result keeps A before B.

Merge sort can be stable, but stability is not automatic in every implementation. When the two candidates compare equal, the merge must take the value from the left half first. That is why the numeric example uses <= rather than <.

For objects, the merge function would normally accept a comparator. If the comparator reports equality, choosing the left candidate preserves the order established before the split.

The hidden cost of removing from the front

A first merge implementation may repeatedly call shift():

while (left.length && right.length) {
  result.push(left[0] <= right[0] ? left.shift() : right.shift());
}

It resembles the mental model of “take the first value,” but JavaScript arrays are indexed collections, not linked queues. The specified behaviour of shift() moves the remaining indexed properties toward the start and reduces length. Repeating that operation can add substantial element-moving work.

At the abstract-algorithm level, merging two sorted sequences of total length m requires Θ(m) comparisons and selections. If every front removal itself moves a number of remaining array elements, a shift-based implementation can make one merge approach quadratic work in m, undermining the complexity expected from merge sort.

Using cursor indices preserves the intended linear merge. This is a useful lesson beyond this algorithm: Big O reasoning must include the cost of the language operations used to implement each abstract step.

No benchmark is presented here. Exact performance would require a reproducible script, runtime version, input generation method, warm-up policy, and an explanation of what the measurement can and cannot establish.

A learning reflection

The difficult part of merge sort was not writing Math.floor(values.length / 2). It was recognizing the contract between the two phases:

• a recursive call promises to return a sorted version of a smaller input; and
• merge promises to produce one sorted result when given two sorted inputs.

The base case makes the first promise trivially true for arrays of length zero or one. Each parent call can then rely on its children, merge their results, and satisfy the same promise at a larger size.

That contract is the core of the recursive reasoning. Drawing the calls down to single elements and then tracing their return values back up is more informative than staring only at the final implementation.

All demonstrated JavaScript output in this article was verified with Node.js v22.23.1.

Key takeaways

• Merge sort separates recursive splitting from ordered merging.
• Arrays of length zero or one form the base case because they are already sorted.
• Every recursive call must receive a smaller problem.
• A parent call merges only after its two recursive calls return sorted halves.
• Two sorted arrays can be merged in linear time by advancing cursor indices.
• Standard merge sort takes Θ(n log n) time and uses linear auxiliary array space, plus a logarithmic recursion stack.
• Merge sort is stable only when the merge rule preserves the order of equal values, commonly by choosing the left value first.
• Repeated front removal with shift() can make the JavaScript implementation more expensive than the abstract algorithm suggests.
• This article demonstrates the method but does not claim details about an unavailable earlier project implementation.

Sources

• The Odin Project: Recursion
• MDN: Recursion glossary
• Thomas H. Cormen et al., Introduction to Algorithms, fourth edition
• MDN: Array.prototype.shift()