Educatifu
Open menu

Merge Sorted Arrays

Mediumarraystwo-pointers

Merge two already-sorted arrays into one sorted array.

Input

Line 1: an integer n. Line 2: n integers in non-decreasing order. Line 3: an integer m. Line 4: m integers in non-decreasing order (this line is empty when m is 0).

Output

All n + m numbers in non-decreasing order, separated by single spaces.

Examples

Example 1

Input
3
1 3 5
3
2 4 6
Output
1 2 3 4 5 6

Interleaves to 1 2 3 4 5 6.

Example 2

Input
1
5
1
3
Output
3 5

Two singletons merge to 3 5.

Example 3

Input
3
1 2 3
2
4 5
Output
1 2 3 4 5

The second array simply follows.

Constraints

  • 0 <= n, m <= 10^5
  • Both input arrays are sorted in non-decreasing order.

Hints

Reveal hint 1

Because both inputs are already sorted, you can merge them with two pointers in linear time.

Reveal hint 2

Repeatedly take the smaller of the two current front elements.

Reference solution (spoiler — try it yourself first)

Approach

Two-pointer merge (or concatenate then sort). Emit the combined values in non-decreasing order.

import sys
d = list(map(int, sys.stdin.read().split()))
n = d[0]
a = d[1:1 + n]
m = d[1 + n]
b = d[2 + n:2 + n + m]
print(' '.join(map(str, sorted(a + b))))

← All practice problems

Bring us the problem, not a perfect specification

Tell us what needs to change, who it affects and any important deadline. We will review the context and reply with useful next questions.

  1. 01Share contextDescribe the workflow, constraint or risk.
  2. 02Clarify togetherWe identify missing facts and useful options.
  3. 03Choose a startAgree a focused assessment or delivery step.
Start a conversation