Merging two sorted integer arrays in place using $O(n)$ time and $O(1)$ space is a common problem that comes up in various computer science applications. While the traditional approach of merging involves using additional space to store the merged arrays, it is possible to do it in place, thereby keeping the space complexity constant. This article explores in depth the technique to achieve this.

Problem Statement

You are given two sorted integer arrays `arr1` and `arr2`, where `arr1` has sufficient space at the end to accommodate the elements of `arr2`. The goal is to merge these arrays in a way that results in a single sorted array contained within `arr1`, using $O(n)$ time and $O(1)$ additional space.

Prerequisites

• Arrays: Understanding of basic array operations.
• In-Place Operations: Understanding how to manipulate elements in arrays without using additional storage.
• Sorting Algorithms: Familiarity with basic sorting principles.

Algorithm Explanation

The essence of the in-place merge algorithm is to use the existing space at the end of `arr1` to accommodate all elements. This algorithm functions by iterating backward through `arr1` and `arr2`, placing the largest element in the correct position from the end of `arr1`.

Steps to Merge

1. Initialization:
   • Let `m` be the number of elements initially present in `arr1` (excluding extra space).
   • Let `n` be the number of elements in `arr2`.
   • Set `i = m - 1` to point to the last valid element in `arr1`.
   • Set `j = n - 1` to point to the last element of `arr2`.
   • Set `k = m + n - 1` to point to the last position in `arr1`.
2. Iteration:
   • While `j >= 0`:
     • Compare elements `arr1[i]` and `arr2[j]`.
     • Place the greater of the two in `arr1[k]`.
     • Move the appropriate index (`i`, `j`, or both) and decrement `k`.
   • If any elements remain in `arr2`, copy them to `arr1`. This step is necessary because all remaining elements in `arr1` are already in place.
3. Time Complexity: The entire process involves a single iteration over the two arrays, making the time complexity $O(n + m)$.
4. Space Complexity: The algorithm uses no additional space apart from variables used for indices, hence $O(1)$.

Example

Consider the following example for clarity:

• `arr1 = [1, 3, 5, 0, 0, 0]` and `arr2 = [2, 4, 6]`
• Initial indices: `i = 2`, `j = 2`, `k = 5`

Merge Process:

Edge Cases

• Empty `arr2`: If `arr2` is empty, `arr1` remains unchanged.
• Empty `arr1` (besides extra space): All elements of `arr2` must be directly copied to the front of `arr1`.
• Identical Elements: Handles duplicates by merging them in sequence.

Conclusion

Merging two sorted arrays in place without using extra space is both efficient and essential for working within memory constraints. This algorithm can be extended to similar data merging problems, allowing for effective data processing with minimal overhead. This straightforward yet elegant solution showcases the powerful combination of algorithmic analysis and optimal space usage.