Merge Sorted Arrays

ArraySortingTwo Pointers

Given two sorted arrays arr1 and arr2, your task is to merge these arrays into one sorted array and return the resulting array.

The function should take two lists of integers as input and return a single list of integers which is sorted.

Example 1

Input

Output

[1, 2, 3, 4, 5, 6]

Explanation. Inserted all elements from both arrays into a single list in sorted order.

Example 2

Input

[
  [
    -1,
    -1,
    2
  ],
  [
    0,
    3
  ]
]

Output

[-1, -1, 0, 2, 3]

Explanation. Handled negative values correctly alongside positive values and zeros, maintaining sorted order.

Example 3

Input

[
  [],
  [
    1,
    2,
    3
  ]
]

Output

[1, 2, 3]

Explanation. Even when one of the arrays is empty, the algorithm correctly outputs the non-empty input array as result.

Example 4

Input

Output

[10, 15, 20, 25, 30]

Explanation. Properly merged arrays where the elements interleave.

Example 5

Input

Output

[1, 2, 3, 4, 5, 5]

Explanation. Correctly handles duplicates between the two arrays.

Follow-up: Can you achieve this with O(n + m) time complexity, where n and m are the lengths of `arr1` and `arr2`, respectively?

Constraints:

Each input array may contain anywhere from 1 to 5000 elements. Each element in the arrays will be an integer in the range `[-10^6, 10^6]`. The result must not use any built-in sort functions.

Views: 2