Merge Two Sorted Lists

Problem

Merge two sorted lists into one sorted list.

Both inputs are sorted in non-decreasing order and may be empty. Use two pointers to interleave values, taking from a when a[i] is less than or equal to b[j], then append any leftovers.

Return the merged list.

Hint

Compare the current heads, take the smaller one, and drain the remaining list at the end.

Test cases

case 1

in: [[1,2,4],[1,3,4]]

expected: [1,1,2,3,4,4]

case 2

in: [[],[1,2]]

expected: [1,2]

case 3

in: [[],[]]

expected: []

case 4

in: [[0],[-1,5]]

expected: [-1,0,5]

Starter codePython

def merge_sorted(a, b):
    # Your code here
    pass

4 test cases · run your code against them in the editor