Merge Sorted Arrays

You are tasked with merging two sorted arrays into a single sorted array. This is a fundamental operation in computer science, often encountered in algorithms like merge sort and in database operations where data from multiple sources needs to be combined efficiently. A correct and efficient solution will ensure that the resulting array maintains its sorted order.

Problem Description

Given two sorted arrays, array1 and array2, merge them into a new single sorted array.

Key Requirements:

• The resulting array must contain all elements from both array1 and array2.
• The resulting array must be sorted in non-decreasing order.
• The original array1 and array2 should not be modified.

Expected Behavior:

The function should return a new array that is the result of combining and sorting the elements of array1 and array2.

Edge Cases to Consider:

• One or both arrays might be empty.
• Arrays might contain duplicate elements.
• Arrays might have different lengths.

Examples

Example 1:

Input:
array1 = [1, 3, 5, 7]
array2 = [2, 4, 6, 8]

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

Explanation: All elements from both arrays are combined and sorted.

Example 2:

Input:
array1 = [0, 3, 4, 31]
array2 = [4, 6, 30]

Output:
[0, 3, 4, 4, 6, 30, 31]

Explanation: Elements from both arrays are merged, including the duplicate '4'.

Example 3: (Edge Case)

Input:
array1 = []
array2 = [1, 2, 3]

Output:
[1, 2, 3]

Explanation: Merging an empty array with a non-empty array results in the non-empty array itself.

Example 4: (Edge Case)

Input:
array1 = [5]
array2 = []

Output:
[5]

Explanation: Merging a non-empty array with an empty array results in the non-empty array itself.

Constraints

• The number of elements in array1 will be between 0 and 1000, inclusive.
• The number of elements in array2 will be between 0 and 1000, inclusive.
• Elements in both array1 and array2 will be integers.
• Elements within each input array will be sorted in non-decreasing order.
• Your solution should aim for an efficient time complexity.

Notes

Consider how you can iterate through both arrays simultaneously, comparing elements and placing them into the new array in the correct order. Think about what happens when one array runs out of elements before the other.