Merge Sort Visualizer

Merge sort is the first algorithm most people meet that is genuinely clever rather than merely correct. The insight behind it — that merging two already-sorted lists is easy, and that everything is already sorted if you cut it small enough — is the template for divide and conquer, and it turns up again in everything from parallel computing to database joins.

It is also the sort you choose when you cannot afford to be unlucky. Quick sort is usually faster, but 'usually' has a worst case of O(n²). Merge sort is O(n log n) on every input that has ever existed or ever will, which is why it underpins external sorting, stable library sorts, and anything with a latency guarantee attached.

What is merge sort?

Merge sort splits the array in half, sorts each half recursively, and then merges the two sorted halves into one. The recursion bottoms out at sub-arrays of length one, which are sorted by definition — there is nothing to compare.

All the actual work happens in the merge. Given two sorted lists, you can produce one sorted list by repeatedly taking whichever front element is smaller. Each comparison places exactly one element, so merging two lists of total length n costs n−1 comparisons at most and touches each element once.

That is the whole algorithm. The splitting is bookkeeping; the merging is the algorithm. It is worth being precise about this, because it explains where the O(n) extra memory goes and why merge sort is stable.

Why it works

Correctness follows by induction on the length of the sub-array. Base case: a sub-array of length one is sorted. Inductive step: assume both recursive calls correctly sort their halves. The merge then produces a sorted result, because at each step it takes the smallest remaining element across both halves — and since each half is sorted, the smallest remaining element in each is its front element, so comparing just those two is sufficient.

The cost analysis is equally clean. Splitting halves the problem, so the recursion is log₂n levels deep. At every level, the merges collectively touch all n elements exactly once. Total work is therefore n operations per level × log n levels = O(n log n), and this argument makes no assumption whatsoever about the data. Sorted, reversed, random and adversarial inputs all cost the same.

The recurrence, if you prefer it formally, is T(n) = 2T(n/2) + Θ(n), which by the master theorem gives Θ(n log n).

Step-by-step walkthrough

Take [38, 27, 43, 3, 9, 82, 10]. The split phase does no comparing at all; it just cuts.

1. Split into [38, 27, 43, 3] and [9, 82, 10], then keep splitting until every piece is a single element.
2. Merge [38] and [27]: compare, take 27, then 38 → [27, 38]. Merge [43] and [3] → [3, 43].
3. Merge [27, 38] and [3, 43]: take 3, then 27, then 38, then 43 → [3, 27, 38, 43]. Three comparisons for four elements.
4. On the right, merge [9] and [82] → [9, 82], then merge with [10] → [9, 10, 82].
5. Final merge of [3, 27, 38, 43] and [9, 10, 82] produces [3, 9, 10, 27, 38, 43, 82].

The memory cost, and why it is unavoidable

Merging cannot be done comfortably in place. To write the merged result back into the original array you must first copy at least one of the halves elsewhere, because writing into position 0 would overwrite an element you have not yet read. That copy is where O(n) auxiliary space comes from, and it is merge sort's one real weakness.

In-place merge algorithms exist. They are genuinely difficult, and they trade the extra memory for a substantially worse constant factor or an O(n log² n) time bound — usually a bad deal. The practical answer, used by real implementations, is to allocate a single scratch buffer of size n once at the start and reuse it for every merge, rather than allocating inside the recursion.

There is one context where the memory cost inverts into an advantage: external sorting, where the data does not fit in RAM at all. Merge sort's access pattern is purely sequential, so it can merge sorted runs streaming from disk or tape with minimal seeking. This is how databases sort result sets larger than memory, and no in-place algorithm comes close.

How the animation above works

The violet band marks the sub-array currently being worked on, so you can watch the recursion narrow to individual elements and then widen again as merges complete. Coral flashes mark writes back into the array — merge sort writes far more than it swaps, because it does not swap at all.

Two things are worth watching for specifically. First, the comparison counter grows smoothly and predictably regardless of which starting arrangement you pick; switch between random, reversed and nearly-sorted and the totals barely move. That invariance *is* the guaranteed O(n log n). Second, at size 200 compare the total against bubble sort in the comparison lab — roughly 1,500 operations against roughly 20,000.

Time complexity

O(n log n) in the best, average and worst case. The recursion depth is log₂n and each level does Θ(n) work merging. No input distribution changes either factor.

The precise comparison count is between roughly n log₂n − n + 1 and n log₂n, depending on how the merges break. For 1,000 elements that is under 10,000 comparisons, against roughly 500,000 for an O(n²) sort — the practical meaning of the difference between the two complexity classes.

The one genuine inefficiency: standard merge sort does not adapt. An already-sorted array still costs the full O(n log n), where insertion sort would finish in O(n). Timsort exists precisely to fix this, by detecting already-ordered runs in the input and merging those instead of splitting blindly to single elements.

Space and stability

O(n) auxiliary space for the merge buffer, plus O(log n) stack space for the recursion. The linked-list variant needs only O(log n) total, since merging a list is a matter of relinking nodes rather than copying values.

Stable, and the reason is a single character. The merge takes from the left half when left[i] <= right[j]. That <= rather than < means a tie is resolved in favour of the element that was originally earlier, so equal elements never cross. Flip it to < and merge sort silently becomes unstable while still producing correctly sorted output — a bug that unit tests on integers will never catch.

Stability is why merge sort, not quick sort, is the basis of Java's Arrays.sort() for objects and of Python's sorted(). When you sort a table by date and then by name, stability is what keeps the dates in order within each name.

Complexity at a glance

The numbers below are what the counters in the visualiser converge on. Raise the array size and watch the comparison count grow at the rate this table predicts.

Pseudo code

Language-agnostic, and close enough to the implementations below that you can read them side by side.

Merge Sort in five languages

Working reference implementations — copy or download any of them. They are written to be read, so the comments explain the decisions rather than restating the code.

/**
 * Top-down merge sort. Guaranteed O(n log n) on every input, and stable.
 * Returns a new array rather than sorting in place.
 */
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);
}

function merge(left, right) {
  const out = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    // <= (not <) resolves ties in favour of the left half, which is what
    // makes the whole sort stable.
    if (left[i] <= right[j]) out.push(left[i++]);
    else out.push(right[j++]);
  }

  // Exactly one of these still has elements left.
  while (i < left.length) out.push(left[i++]);
  while (j < right.length) out.push(right[j++]);

  return out;
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));

Advantages and disadvantages

Real-world applications

• External sorting in databases and data warehouses, where the dataset exceeds RAM and sequential disk access is what matters.
• The merge phase of MapReduce and similar distributed frameworks, which combine sorted partial results from many machines.
• Java's Arrays.sort() for object arrays and Python's sorted() — both use Timsort, an adaptive merge sort built around detecting existing runs.
• Counting inversions in a sequence, which merge sort computes in O(n log n) as a by-product of the merge step.
• Sorting linked lists, where merge sort is the standard answer because it needs no random access and no extra memory.
• Any system with a hard latency requirement, where quick sort's rare O(n²) worst case is unacceptable regardless of its average speed.

Interview questions

The questions that actually get asked about Merge Sort, with the answers an interviewer is listening for.

1. Q1. Why is merge sort O(n log n) in the worst case when quick sort is O(n²)?

   Because merge sort splits by index at the midpoint, which the data cannot influence — every split is perfectly balanced by construction, so the recursion is always exactly log₂n deep. Quick sort splits by value around a pivot, so an unlucky or adversarial pivot choice can produce partitions of size 1 and n−1, making the recursion n levels deep.

2. Q2. What makes merge sort stable, and how would you accidentally break it?

   The merge takes from the left half when left[i] <= right[j]. Because the left half holds the originally-earlier elements, resolving ties towards the left preserves their order. Changing that to < breaks stability while still producing a correctly sorted array — a bug invisible to any test that sorts plain integers.

3. Q3. Can merge sort be done in place, and should it be?

   In-place merge algorithms exist, but they are complex and either carry a much larger constant factor or push the complexity to O(n log² n). In practice you get most of the benefit by allocating one scratch buffer of size n up front and reusing it, instead of slicing inside the recursion. On linked lists the question disappears — merging relinks nodes and needs no extra space at all.

4. Q4. How would you use merge sort to count inversions in an array?

   During the merge, when you take an element from the right half while i elements remain unconsumed in the left half, those i elements are each greater than the one you just took — so add (mid − i + 1) to the inversion count. Summing across all merges gives the total in O(n log n), versus O(n²) for the brute-force approach.

5. Q5. What is Timsort and how does it improve on plain merge sort?

   Timsort is an adaptive merge sort. Instead of splitting blindly down to single elements, it scans for runs already in ascending or descending order, extends short runs with binary insertion sort, and then merges the runs using a stack with balancing rules. On real-world data — which is usually partly ordered — this approaches O(n), while retaining merge sort's O(n log n) guarantee in the worst case.

Common mistakes

• Using < instead of <= when comparing the two halves during the merge, which silently destroys stability.
• Allocating new arrays inside the recursion via slice, which produces O(n log n) total allocation and often dominates the running time.
• Computing the midpoint as (lo + hi) / 2, which overflows for large indices in fixed-width integer languages — lo + (hi - lo) / 2 never does.
• Forgetting to copy the remainder of whichever half still has elements after the main merge loop ends.
• Passing exclusive and inclusive bounds inconsistently between the recursive calls and the merge, producing off-by-one errors that are hard to spot because the output is often *nearly* sorted.
• Recursing on (lo, mid) and (mid, hi) instead of (mid + 1, hi), which causes infinite recursion when the range has two elements.

Optimisation tips

• Skip the merge entirely when arr[mid] <= arr[mid + 1] — the halves are already ordered across the seam. This one line makes merge sort O(n) on sorted input.
• Switch to insertion sort for sub-arrays below roughly sixteen elements; it cuts the constant factor noticeably by eliminating the deepest, most overhead-heavy levels of recursion.
• Allocate the scratch buffer once outside the recursion and reuse it for every merge.
• Alternate the roles of the array and the buffer between levels so the copy-back step disappears — merge from A into B on one level, B into A on the next.
• Use the bottom-up iterative form (merge widths of 1, then 2, then 4…) to avoid recursion entirely, which is also easier to parallelise.
• For real-world partly-ordered data, implement run detection — that is the step from merge sort to Timsort, and it is where the practical gains are.

Summary

Merge sort recursively halves the array, sorts each half, and merges the sorted halves back together. Because the split is by index rather than by value, the recursion is always exactly log₂n levels deep and each level costs Θ(n), giving a guaranteed O(n log n) on every possible input.

The price is O(n) auxiliary memory, which is the one thing that keeps it from being the universal default. In exchange you get stability, predictable timing, sequential access suited to external sorting, and a structure that parallelises cleanly. When you cannot risk quick sort's worst case, or when you need stable sorting of records, merge sort is the answer — and Timsort, the adaptive merge sort in Python and Java, is what most production code is actually running.

Frequently asked questions

Related algorithms

• Quick Sort

  Partition around a pivot so everything smaller lands left and larger lands right.

  O(n log n)Intermediate

• Heap Sort

  Build a max-heap, then repeatedly pull the root to the end of the array.

  O(n log n)Advanced

• Insertion Sort

  Grow a sorted prefix by sliding each new value back to where it belongs.

  O(n²)Beginner