Implement in-place merge sort
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]
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;}