Sorting · stretch

Merge sort

Write merge_sort(items) returning a new sorted list: split in half, merge_sort each half, then merge the two sorted halves.

A list of 0 or 1 items is already sorted — that is the base case.

right answers
arguments left as they should be
fast enough at scale
without sorted, sort, heapq, min

def merge_sort(items):
    result = list(items)
    for i in range(1, len(result)):
        current = result[i]
        j = i - 1
        while j >= 0 and result[j] > current:
            result[j + 1] = result[j]
            j -= 1
        result[j + 1] = current
    return result

Run adds print(merge_sort([5, 2, 9, 1, 5, 6])) after your code, to try it.

Stuck on the idea rather than the code? The Merge sort, and sorting by a key lesson walks through it.