Implement Merge-sort in-place

Problem Statement

Implement merge sort algorithm without using any extra space (in-place). The standard merge sort uses O(n) auxiliary space for merging. The challenge is to merge two sorted subarrays in-place.

Constraints:

• 1 ≤ N ≤ 10^5
• Array elements can be any integers

Example:

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

Example 2:

• Input: arr = [5, 4, 3, 2, 1]
• Output: [1, 2, 3, 4, 5]

Background: Standard Merge Sort

Standard merge sort uses O(n) extra space:

Approach 1: In-Place Merge with Rotations

Intuition

When we find an element in the right half that should come before an element in the left half, we rotate the elements to make space.

Algorithm

1. Use standard merge sort division
2. In merge step, when right element is smaller:
   • Store the right element
   • Shift all elements between current left position and right position
   • Place the stored element at the correct position

public class InPlaceMergeSort {
    private void merge(int[] arr, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        
        if (arr[mid] <= arr[j]) return;
        
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                i++;
            } else {
                int value = arr[j];
                int index = j;
                
                while (index != i) {
                    arr[index] = arr[index - 1];
                    index--;
                }
                
                arr[i] = value;
                
                i++;
                mid++;
                j++;
            }
        }
    }
    
    public void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    
    public void sort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }
}

Complexity Analysis

• Time Complexity: O(n² log n) - Each merge can be O(n²) due to shifting
• Space Complexity: O(log n) - Recursion stack only

Approach 2: Gap Method (Shell Sort Style) - Optimal

Intuition

Use the gap method (similar to Shell sort). Start with a large gap and reduce it, swapping elements that are out of order with respect to the gap.

Algorithm

1. Start with gap = ceil(n/2)
2. Compare elements at distance = gap
3. If out of order, swap
4. Reduce gap: gap = ceil(gap/2)
5. Continue until gap = 0

public class InPlaceMergeSortGap {
    private int nextGap(int gap) {
        if (gap <= 1) return 0;
        return (gap / 2) + (gap % 2);
    }
    
    private void merge(int[] arr, int left, int mid, int right) {
        int gap = nextGap(right - left + 1);
        
        while (gap > 0) {
            int i = left;
            
            while (i + gap <= right) {
                if (arr[i] > arr[i + gap]) {
                    int temp = arr[i];
                    arr[i] = arr[i + gap];
                    arr[i + gap] = temp;
                }
                i++;
            }
            
            gap = nextGap(gap);
        }
    }
    
    public void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    
    public void sort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n log n) - Gap reduces logarithmically, each pass is O(n)
• Space Complexity: O(log n) - Recursion stack only

Approach 3: Block-Based In-Place Merge

This is a more complex but theoretically optimal approach:

Comparison of Approaches

| Approach | Time | Space | Stability | |----------|------|-------|-----------| | Rotation-based | O(n² log n) | O(log n) | Stable | | Gap method | O(n log²n) | O(log n) | Not Stable | | Block merge | O(n log n) | O(1) | Can be stable | | Standard merge | O(n log n) | O(n) | Stable |

Practical Considerations

Key Takeaways

1. Trade-offs: In-place merge sacrifices time complexity or stability for space
2. Gap Method: Most practical O(n log²n) in-place approach
3. Rotation Method: Maintains stability but O(n² log n) time
4. Block Merge: Theoretically optimal but complex to implement
5. Hybrid Approach: Combine with insertion sort for small arrays
6. When to Use: Memory-constrained environments, embedded systems
7. Alternative: Consider using heapsort (O(n log n), O(1) space, in-place)