Iteration

Merge

Sorting

Given two sorted arrays arr1 and arr2, merge them together and return the new array.

This is a prerequisite to MergeSort.

Example:

Merge - image
arr1 = [3,6,8,10]arr2 = [1,4,5,7,8,9]=> returns [1,3,4,5,6,7,8,8,9,10]\notag \texttt{arr1 = [3,6,8,10]} \\ \texttt{arr2 = [1,4,5,7,8,9]} \\[8bp] \texttt{=> returns [1,3,4,5,6,7,8,8,9,10]}
First Few Test Cases:
merge([1, 3], [2, 4])
# [1, 2, 3, 4]
merge([], [1, 2])
# [1, 2]
merge([3, 6, 8, 10], [1, 4, 5, 7, 8, 9])
# [1, 3, 4, 5, 6, 7, 8, 8, 9, 10]

One idea is to simply concatenate the arrays and call sort. That's an O(nlog⁡n)O(n \log n) time complexity algorithm. It turns out we can do much better than that. An indication we can do better is that the concatenate algorithm doesn't take advantage of the fact that the arrays are sorted at all.

The idea to solving this problem is to start with a blank array, and add elements in increasing order.

Merge - image

The trick to doing this is that the smallest value is guaranteed to be the leftmost element in one of the arrays, because they're sorted. We can take whatever leftmost element is smaller, and add it to our solution.

Merge - image

We can keep repeating this, comparing the leftmost values in the two arrays, and adding whatever is smaller to our solution.

Merge - image

Here's the code:

def merge(arr1, arr2):
    i = 0 # index in `arr1`
    j = 0 # index in `arr2`

    solution = []
    
    # while both of the arrays contains elements
    while i != len(arr1) and j != len(arr2):
        # add the smallest element to the solutions
        if arr1[i] < arr2[j]:
            solution.append(arr1[i])
            i += 1
        else:
            solution.append(arr2[j])
            j += 1

    # now one of the arrays is empty, so add all the remaining elements to solution
    solution.extend(arr1[i:])
    solution.extend(arr2[j:])
    
    return solution

Time Complexity O(n)O(n), where nn is the total number of elements.

Space Complexity O(n)O(n) to store the merged array.

Mark as Completed:
Submits:
merge
Test your code to get an output here!
merge(
)
Test your code to get an output here!