Implement in-place merge sort

Hard

Problem

Sort an array with merge sort, but merge the two halves inside the array itself rather than into an auxiliary array. Explain the time-and-space trade-off this makes.

Example 1

Input:  [12, 11, 13, 5, 6, 7]
Output: [5, 6, 7, 11, 12, 13]

Also asked as: Implement Merge-sort in-place

Test cases

Case 1

Input:    [12,11,13,5,6,7]
Expected: [5,6,7,11,12,13]

Case 2

Input:    [3,1,2,3,1]
Expected: [1,1,2,3,3]

Case 3

Input:    [5,4,3,2,1]
Expected: [1,2,3,4,5]

Case 4

Input:    [1]
Expected: [1]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Merge sort with the gap (Shell) merge

Time O(n log² n)Space O(log n) recursion

Standard recursive split, but merge the two halves in place using the decreasing-gap comparison-and-swap instead of a temp buffer.

function mergeSortInPlace(a, lo = 0, hi = a.length - 1) {
if (lo >= hi) return a;
const mid = (lo + hi) >> 1;
mergeSortInPlace(a, lo, mid);
mergeSortInPlace(a, mid + 1, hi);
let gap = Math.ceil((hi - lo + 1) / 2);
while (gap > 0) {
for (let i = lo; i + gap <= hi; i++)
if (a[i] > a[i + gap]) [a[i], a[i + gap]] = [a[i + gap], a[i]];
gap = gap === 1 ? 0 : Math.ceil(gap / 2);
}
return a;
}