Efficiently Merging Two Sorted Arrays Using a Two-Pointer Technique

The process of merging two sorted arrays into one sorted array can be accomplished efficiently using a two-pointer technique. This method leverages the pre-sorted nature of the arrays, allowing for a straightforward and effective solution. In this article, we will discuss the algorithm in detail and provide examples and code implementations.

Algorithm Overview

The algorithm involves initializing pointers for each array and a combined result array. Here’s how it works:

Step-by-Step Algorithm

Initialize Pointers: Start with two pointers, one for each array. Let's denote them as i for the first array and j for the second array. Initialize both i and j to 0.

Create Result Array: Create an empty array or list named merged, which will store the elements of the combined sorted array.

Compare Elements: While both pointers are within the bounds of their respective arrays:

Compare the elements at array1[i] and array2[j]. If array1[i] array2[j], append array1[i] to merged and increment i. Otherwise, append array2[j] to merged and increment j.

Add Remaining Elements: After the loop, one of the arrays might still have remaining elements. Append these remaining elements to merged:

If i is less than the length of array1, append all remaining elements from array1 to merged. If j is less than the length of array2, append all remaining elements from array2 to merged.

Return Result: The merged array now contains all elements from both arrays in sorted order.

Python Implementation

Here is the Python implementation of the algorithm:

highlightdef merge_sorted_arrays(array1, array2):    merged  []    i, j  0, 0    while i  len(array1) and j  len(array2):        if array1[i]  array2[j]:            (array1[i])            i   1        else:            (array2[j])            j   1    # Add remaining elements    if i  len(array1):        merged.extend(array1[i:])    if j  len(array2):        merged.extend(array2[j:])    return merged/highlight

Example Usage

Let's see an example usage of the function with two sorted arrays:

highlightarray1  [1, 3, 5]array2  [2, 4, 6]result  merge_sorted_arrays(array1, array2)print(result)  # Output: [1, 2, 3, 4, 5, 6]/highlight

Time Complexity

The time complexity of this algorithm is O(n m), where n is the length of array1 and m is the length of array2. This is an efficient solution since each element from both arrays is processed exactly once.

Space Complexity

The space complexity is O(n m) for the resulting merged array, which holds all elements from both input arrays. This space is necessary to store the final sorted array.

Keywords: sorted arrays, two-pointer technique, algorithm, time complexity, space complexity