Practice/Meta/Merge Three Sorted Arrays

Merge Three Sorted Arrays

CodingMust

Problem

You are given three arrays, each already sorted in ascending order. Your task is to combine all three arrays into a single array that maintains sorted order.

Write a function that takes three sorted integer arrays as input and returns one sorted array containing all elements from the three input arrays.

Requirements

1. The input arrays are already sorted in non-decreasing order
2. The output must be a single sorted array containing all elements
3. Preserve duplicate values if they exist across arrays
4. Handle edge cases including empty arrays

Constraints

• 0 ≤ length of each array ≤ 1000
• -10⁴ ≤ array elements ≤ 10⁴
• Your solution should be more efficient than simply concatenating and sorting
• Aim for O(n₁ + n₂ + n₃) time complexity where n₁, n₂, n₃ are the lengths of the three arrays

Examples

Example 1:

Input: arr1 = [1, 4, 7] arr2 = [2, 5, 8] arr3 = [3, 6, 9] Output: [1, 2, 3, 4, 5, 6, 7, 8, 9] Explanation: Elements are interleaved from all three arrays in sorted order

Example 2:

Input: arr1 = [1, 5] arr2 = [2, 3, 4] arr3 = [6, 7, 8, 9, 10] Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] Explanation: Even with different lengths, all elements merge in order

Example 3:

Input: arr1 = [1, 3, 5] arr2 = [] arr3 = [2, 4, 6] Output: [1, 2, 3, 4, 5, 6] Explanation: Empty arrays are handled gracefully