Merging Sorted Arrays

Answer

To merge two pre-sorted arrays into a single sorted array, we can utilize a technique that efficiently combines elements from both arrays in a sorted manner. The primary approach here is to use a two-pointer technique, which allows us to traverse both arrays simultaneously and append the smaller element to the resulting array. This method ensures that the final array is sorted and can be achieved in linear time, O(n+m), where n and m are the lengths of the two input arrays.

Detailed Steps

1. Initialize Pointers: Start by initializing two pointers, i and j, to zero. These pointers will help us keep track of the current position in each of the input arrays.

2. Create Result Array: Create a new array, arr_3, which will store the merged and sorted elements from both input arrays.

3. Iterate Through Arrays:

   • Use a while loop to iterate through both arrays as long as neither pointer has reached the end of its respective array.
   • Compare the current elements pointed to by i and j in arr_1 and arr_2, respectively.
   • Append the smaller element to arr_3 and move the corresponding pointer forward by one.

4. Handle Remaining Elements:

   • After one of the arrays is fully traversed, there may still be remaining elements in the other array. Use two additional while loops to append any remaining elements to arr_3.

5. Return Result: Once both arrays have been completely traversed and merged, return the arr_3 as the final sorted array.

Implementation

def merge_arrays(arr_1, arr_2):
    arr_3 = []
    i = 0
    j = 0
    x = len(arr_1)
    y = len(arr_2)

    # Traverse both arrays
    while i < x and j < y:
        if arr_1[i] < arr_2[j]:
            arr_3.append(arr_1[i])
            i += 1
        else:
            arr_3.append(arr_2[j])
            j += 1

    # Append remaining elements of arr_1
    while i < x:
        arr_3.append(arr_1[i])
        i += 1

    # Append remaining elements of arr_2
    while j < y:
        arr_3.append(arr_2[j])
        j += 1

    return arr_3

# Example Usage
arr_1 = [1, 2, 9, 11]
arr_2 = [3, 4, 6, 8]
print(merge_arrays(arr_1, arr_2))  # Output: [1, 2, 3, 4, 6, 8, 9, 11]

Complexity Analysis

• Time Complexity: O(n+m), where n is the length of arr_1 and m is the length of arr_2. This is because each element from both arrays is processed exactly once.
• Space Complexity: O(n+m) for storing the merged array arr_3.