Merge Two Sorted Arrays in Python

Problem

Given two sorted arrays, merge them into a sorted manner.

Examples

• Example 01

Input: arr1 = [3, 5, 6, 10], arr2 = [1, 2, 7, 8, 11, 12]
Output: arr3 = [1, 2, 3, 5, 6, 7, 8, 10, 11, 12]

• Example 02

Input: arr1 = [1, 3, 4, 5], arr2 = [2, 4, 6, 8]
Output: arr3 = [1, 2, 3, 4, 4, 5, 6, 8]

• Example 03

Input: arr1 = [5, 8, 9], arr2 = [4, 7, 8]
Output: arr3 = [4, 5, 7, 8, 8, 9]

Solution 01

Pseudocode

1. Create an array arr3 by concatenatingarr1 and arr2.
2. Sort arr3 .

Source code

def merge(num1, num2):
    arr3 = num1+num2
    arr3.sort()
    return arr3
    
arr1 = [3, 5, 6, 10]
arr2 = [1, 2, 7, 8, 11, 12]
assert merge(arr1, arr2) == [1, 2, 3, 5, 6, 7, 8, 10, 11, 12]
arr1 = [1, 3, 4, 5]
arr2 = [2, 4, 6, 8]
assert merge(arr1, arr2) == [1, 2, 3, 4, 4, 5, 6, 8]
arr1 = [5, 8, 9]
arr2 = [4, 7, 8]
assert merge(arr1, arr2) == [4, 5, 7, 8, 8, 9]

Time and Space Complexity

• Time Complexity: O((N+M)log(N+M)). Given N is the number of elements in arr1 and M is the number of elements in arr2 .
• Space Complexity: O(N+M)

Solution 02

Pseudocode

Credits: GeeksForGeeks

1. Create an array arr3 of length/size arr1 + arr2 .
2. Simultaneously traverse arr1 and arr2.

• Pick smaller of current elements in arr1 and arr2 , copy this smaller element to the next position in arr3 and move ahead in arr3 and the array whose element is picked.

3. If there are remaining elements in arr1 or arr2 , copy them in arr3 .

Source code

def merge(num1, num2):
    arr3 = [None]*(len(num1)+len(num2))
    i, j, k = 0, 0, 0
    
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            arr3[k] = arr1[i]
            k += 1
            i += 1
        else:
            arr3[k] = arr2[j]
            k += 1
            j += 1
            
    while i < len(num1):
        arr3[k] = arr1[i];
        k += 1
        i += 1
        
    while j < len(num2):
        arr3[k] = arr2[j];
        k += 1
        j += 1
    
    return arr3
                
arr1 = [3, 5, 6, 10]
arr2 = [1, 2, 7, 8, 11, 12]
assert merge(arr1, arr2) == [1, 2, 3, 5, 6, 7, 8, 10, 11, 12]
arr1 = [1, 3, 4, 5]
arr2 = [2, 4, 6, 8]
assert merge(arr1, arr2) == [1, 2, 3, 4, 4, 5, 6, 8]
arr1 = [5, 8, 9]
arr2 = [4, 7, 8]
assert merge(arr1, arr2) == [4, 5, 7, 8, 8, 9]

Time and Space Complexity

• Time Complexity: O(N+M). Given N is the number of elements in arr1 and M is the number of elements in arr2 .
• Space Complexity: O(N+M)

Takeaways

Thank you for reading this short problem solving question. If anyone knows a better or faster time complexity to solve this question, feel free to comment and feedback. Peace! ✌️