351. Merge Sort - In-Place Merge

Given an array of n integers, sort it in ascending order using merge sort, but implement the merge step without allocating a second array - merge the two sorted halves using only O(1) extra space (for example via block rotations or the gap method), and print the final sorted array.

Input: The first line contains an integer n. The second line contains n space-separated integers, the array to sort. Output: Print the sorted array in ascending order, space-separated, on one line.

1 <= n <= 10^5

This variant exists specifically because standard merge sort's O(n) extra space can be a real, meaningful constraint in memory-limited environments - recognizing WHEN that trade-off is worth making (rarely, in practice, given the time cost) is as important as knowing the technique itself.

You already know how to merge two sorted piles into one sorted pile using a helper pile on the side. This problem asks you to do the exact same merging, but WITHOUT using any extra pile at all - you can only rearrange within the space you already have. Brute force: The straightforward merge sort approach allocates a temporary array, merges into it, then copies back - simple and correct, but uses O(n) extra space, which this specific problem's constraints explicitly rule out. Optimised: Rotation-based merging repeatedly identifies the boundary between the two sorted halves and shifts (rotates) just the necessary elements across that boundary to restore order - each rotation costs time proportional to how far elements need to move, but no second array is ever allocated. The 'gap method' is an alternative: compare elements a shrinking gap apart across the whole merge range (inspired by Shell sort), progressively narrowing the gap until everything settles into sorted order.

Merge in place using rotations: when an out-of-order block of elements from the right half needs to move ahead of a block from the left half, rotate that combined range using the standard three-reversal rotation trick (reverse the left block, reverse the right block, then reverse the whole range) so the relative order within each block is restored while the two blocks swap positions, all using only O(1) extra variables. Because each rotation moves a whole block in one shot rather than shifting element by element, and rotations are applied O(log n) times across the merge hierarchy, this achieves close to n log n time while still using only constant extra space. Time: O(n log^2 n) Space: O(1)

Merge the two sorted halves in place by comparing the first unmerged element of each half; whenever an element from the right half is smaller than the current element of the left half, shift every element between the current position and that element's position one step to the right to make room, then insert it (like an insertion into a sorted prefix). This uses no auxiliary array at all, but the shifting can move O(n) elements for a single misplaced value, so a merge step can degrade to quadratic time. Time: O(n^2) per merge, O(n^2 log n) overall Space: O(1)

Implement standard merge sort, but merge the two sorted halves by copying them into a temporary auxiliary array in sorted order and then copying that result back over the original range. This is the textbook merge sort and is fast and simple, but it directly violates the O(1) extra space requirement by needing an auxiliary array as large as the range being merged. Time: O(n log n) Space: O(n)

1. You have two adjacent sorted halves within the same array (no separate copy). 2. Find the first place where an element from the right half is actually smaller than an element from the left half - that's a violation of sorted order. 3. Rotate just enough elements so that smaller right-half element slides into its correct position among the left half, shifting everything else over by exactly the right amount. 4. Repeat this find-and-rotate process across the whole merge range until both halves are fully interleaved in sorted order.

Time: Slower than the standard O(n log n) merge sort in practice - rotation-based in-place merging typically costs closer to O(n log² n) or O(n²) in the worst case, depending on the exact technique, because shifting elements in place is inherently more expensive than just copying into a fresh array. Space: O(1) extra space (beyond the recursion stack) - genuinely no second array is ever allocated, which is the entire point of this harder variant.

n = 1 (trivial, no merge step needed); n = 10^5 to confirm the O(1)-extra-space merge (rotations or the gap method) stays efficient; duplicate values, which the constraints don't exclude.

This is explicitly a 'harder variant' interview question testing whether you understand the SPACE/TIME trade-off, not just whether you can implement standard merge sort - be ready to explicitly state that this in-place version sacrifices some time efficiency to achieve O(1) extra space.