What algorithmic steps are involved in combining two sorted arrays into one that is also sorted?

Question Analysis

The question is asking about the process of merging two sorted arrays into a single sorted array. This is a common problem that appears in various contexts, such as in the merge step of the Merge Sort algorithm. The key challenge here is to ensure that the final array remains sorted after merging, without using unnecessary additional space or time.

Answer

To merge two sorted arrays efficiently, you can use a two-pointer technique. Here is a step-by-step explanation of how to achieve this:

1. Initialize Pointers:

   • Start by setting two pointers, i and j, to the first elements of the two sorted arrays, A and B, respectively.
   • Initialize an empty array C to store the merged result.

2. Compare and Merge:

   • While both pointers are within the bounds of their respective arrays:
     • Compare the elements pointed to by i in A and j in B.
     • Append the smaller element to the array C.
     • Move the pointer of the array from which the element was taken forward by one position.

3. Append Remaining Elements:

   • If one of the arrays is exhausted before the other, simply append the remaining elements of the non-exhausted array to C.

4. Result:

   • The array C will now contain all the elements from both A and B in sorted order.

Example Code (Python):

def merge_sorted_arrays(A, B):
    i, j = 0, 0
    C = []
    while i < len(A) and j < len(B):
        if A[i] < B[j]:
            C.append(A[i])
            i += 1
        else:
            C.append(B[j])
            j += 1
    C.extend(A[i:])
    C.extend(B[j:])
    return C

# Example usage:
A = [1, 3, 5]
B = [2, 4, 6]
print(merge_sorted_arrays(A, B))  # Output: [1, 2, 3, 4, 5, 6]

Time Complexity: The algorithm runs in O(n + m) time, where n and m are the lengths of the two arrays, since each element is processed exactly once.

Space Complexity: The space complexity is O(n + m) as we create a new array to store the merged result.