Beyond Big O

Merge sorted sequences

Merge sorted sequences

Easy

Your task

  • Merge two inputs sorted in nondecreasing order into one nondecreasing list.
  • Include every value and preserve all duplicate counts.

Required API

  • MergeSorted
    func MergeSorted(a, b []int) []int

Behavior

  • Leave both inputs unchanged.
  • Either input may be empty; if both are empty, return [].

Constraints

  • The input is already valid: the combined length is 0–200, and each integer is between -10,000 and 10,000 inclusive.
  • Use a forward cursor for each input and aim for O(len(a) + len(b)) time.
  • Do not concatenate and sort, use a sorting helper or add dependencies.
  • Do not count output storage in auxiliary-space analysis.
  • Separate calls are independent.
Notes and example notation

Examples use {"a": [...], "b": [...]}.

Examples

The runner calls your functions directly; you do not need to parse JSON.

Example 1 · empty

Arguments
a
[]
b
[]
Expected return
[]
Test data
Input
{"a":[],"b":[]}
Expected output
[]

Example 2 · interleave

Arguments
a
[
  1,
  4,
  8
]
b
[
  2,
  3,
  9
]
Expected return
[
  1,
  2,
  3,
  4,
  8,
  9
]
Test data
Input
{"a":[1,4,8],"b":[2,3,9]}
Expected output
[1,2,3,4,8,9]

Example 3 · duplicates

Arguments
a
[
  1,
  1,
  3
]
b
[
  1,
  2,
  3
]
Expected return
[
  1,
  1,
  1,
  2,
  3,
  3
]
Test data
Input
{"a":[1,1,3],"b":[1,2,3]}
Expected output
[1,1,1,2,3,3]

Example 4 · one empty

Arguments
a
[]
b
[
  -3,
  0,
  2
]
Expected return
[
  -3,
  0,
  2
]
Test data
Input
{"a":[],"b":[-3,0,2]}
Expected output
[-3,0,2]
Editor options
Typing preferences

Saved in this browser.

Restoring local drafts…