BL
U

35. Merge Two Sorted Arrays

Easy

Problem Description

Given two sorted arrays AA of size NN and BB of size MM, merge them into a single sorted array of size N+MN + M.

Input Format

  • •Line 1: Two space-separated integers NN and MM (0≤N,M≤1050 \le N, M \le 10^5, N+M≥1N+M \ge 1).
  • •Line 2: NN sorted integers A1,…,ANA_1, \dots, A_N. (Omitted if N=0N = 0).
  • •Line 3: MM sorted integers B1,…,BMB_1, \dots, B_M. (Omitted if M=0M = 0).

Output Format

Print N+MN + M space-separated integers in non-decreasing order.

Example 1:
Input:
3 3
1 3 5
2 4 6
Output:
1 2 3 4 5 6
Explanation: Merged sorted sequence.
Example 2:
Input:
3 0
1 2 3
Output:
1 2 3
Explanation: Second array is empty.
Example 3:
Input:
2 4
5 10
1 2 8 12
Output:
1 2 5 8 10 12
Explanation: Two unequal sorted arrays merged.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online