Merge two sorted lists in Python

The merge half of merge sort - two pointers over sorted inputs.

def merge_sorted(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    return out + left[i:] + right[j:]

How it works

1. Walks two sorted lists with indexes i and j.
2. Always appends the smaller head to the output.
3. Tacks on whatever remains when one list runs out.

Keywords and builtins used here

• def
• else
• if
• len
• merge_sorted
• return
• while

The run, in numbers

Lines

10

Characters to type

210

Tokens

89

Three-star pace

95 tpm

At the three-star pace of 95 tokens a minute, this run takes about 56 seconds.

Type this snippet

Step 9 of 10 in Collections, step 31 of 72 in Language basics.

← Previous Next →