Merge Two Sorted Arrays

This Python program merges two sorted arrays into a single sorted array. The program assumes that the input arrays are already sorted in non-decreasing order. The output will be a new array containing all elements from the two input arrays, sorted in non-decreasing order.

Program Structure

• Main Function: The main function contains the logic to merge two sorted arrays.
• Merge Function: A separate function to perform the merging of two sorted arrays.

"""
This program merges two sorted arrays into a single sorted array.
"""

def merge_sorted_arrays(array1, array2):
    """
    Merges two sorted arrays into a single sorted array.
    
    :param array1: The first sorted array.
    :param array2: The second sorted array.
    :return: A new sorted array containing all elements from array1 and array2.
    """
    merged_array = []
    i, j = 0, 0

    # Merge arrays while there are elements in both arrays
    while i < len(array1) and j < len(array2):
        if array1[i] <= array2[j]:
            merged_array.append(array1[i])
            i += 1
        else:
            merged_array.append(array2[j])
            j += 1

    # Copy remaining elements of array1, if any
    while i < len(array1):
        merged_array.append(array1[i])
        i += 1

    # Copy remaining elements of array2, if any
    while j < len(array2):
        merged_array.append(array2[j])
        j += 1

    return merged_array

def main():
    array1 = [1, 3, 5, 7]
    array2 = [2, 4, 6, 8]

    merged_array = merge_sorted_arrays(array1, array2)
    
    print("Merged Array:", merged_array)

if __name__ == "__main__":
    main()

Explanation

The program consists of the following parts:

1. merge_sorted_arrays Function: This function takes two sorted arrays as input and returns a new array that is the result of merging the two input arrays. It uses two pointers:
   • i: Tracks the current position in the first array.
   • j: Tracks the current position in the second array.

   The function compares elements from both arrays and appends the smaller element to the merged array. It continues this process until all elements from one of the arrays have been added to the merged array. It then adds any remaining elements from the other array.

2. Main Function: The main function initializes two sorted arrays, calls the merge_sorted_arrays function, and prints the merged array to the console.

Output

When the program is executed, it will output the merged array:

Merged Array: [1, 2, 3, 4, 5, 6, 7, 8]