In-Place Merge Sort Sorting Algorithm & Guide

Divide & Conquer · Article 9 of 62

In-Place Merge Sort

Trade time for memory: merge two sorted halves using rotations, eliminating the O(n) buffer at the cost of an extra log factor on writes.

How it works

A "true" in-place merge is much harder than it looks. The simplest implementation merges by repeatedly finding the next element from the right half that should slot into the left and rotating it into place — typically using block rotations or repeated insertion.

Recurse to sort each half (as in standard merge sort).
To merge two sorted runs A and B sharing a boundary, walk a pointer through A. Whenever you find an element of B that should come before the current A position, rotate it into place.
Repeat until both runs are exhausted.

This variant is in-place (O(1) extra memory beyond the recursion stack) but pays for it with O(n log² n) time in the simple form. More elaborate constructions (Kronrod, Symmerge) achieve O(n log n) in-place merge, but the constant factors are heavy and they're rarely worth using.

Complexity

Best time

O(n log n)

Average time

O(n log² n)

Worst time

O(n log² n)

Extra space

O(log n)

Stable

Yes (simple form)

In-place

Yes

In-place merge sort is mostly an academic curiosity. When you really need both stability and O(1) extra memory, you usually reach for a Block Sort (covered later in the Hybrid section).

Interactive visualization

Pseudocode

procedure inPlaceMergeSort(A, lo, hi):
  if lo < hi:
    m ← (lo + hi) / 2
    inPlaceMergeSort(A, lo, m)
    inPlaceMergeSort(A, m + 1, hi)
    inPlaceMerge(A, lo, m, hi)

procedure inPlaceMerge(A, lo, m, hi):
  while lo ≤ m and m + 1 ≤ hi:
    if A[lo] ≤ A[m + 1]:
      lo ← lo + 1
    else:
      v ← A[m + 1]
      shift A[lo..m] right by 1
      A[lo] ← v
      lo ← lo + 1; m ← m + 1

JavaScript implementation

function inPlaceMergeSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;
  const m = (lo + hi) >> 1;
  inPlaceMergeSort(arr, lo, m);
  inPlaceMergeSort(arr, m + 1, hi);
  inPlaceMerge(arr, lo, m, hi);
  return arr;
}
function inPlaceMerge(arr, lo, m, hi) {
  while (lo <= m && m + 1 <= hi) {
    if (arr[lo] <= arr[m + 1]) { lo++; continue; }
    const v = arr[m + 1];
    for (let j = m + 1; j > lo; j--) arr[j] = arr[j - 1];
    arr[lo] = v; lo++; m++;
  }
}

Pros and cons

Pros

No O(n) auxiliary buffer.
Stable in the rotation-based formulation.
Useful theoretical reference.

Cons

Naïve form is O(n log² n) — slower than standard merge sort.
Many writes (shifts) — bad on flash storage.
Optimal in-place merge is complex and not faster than out-of-place merge sort in practice.
Constant factors dominate cache behavior.

When to use it

Memory-constrained sorts where allocating O(n) is forbidden.
Educational contrast with the standard merge sort.
Embedded systems where stability matters more than micro-optimal time.

Up next: Quick Sort — a tiny one-line change that prevents the O(n²) worst case in the overwhelming majority of inputs.

In-Place Merge Sort: Mechanism, Complexity Analysis & Interactive Visualizer