Merge sort program in Python (recursive)

Merge sort splits the list into two halves, sorts each half with the same function (recursion), and then merges the two sorted halves into one sorted list.

The program

python

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # one list is used up; the rest of the other is already sorted
    return result + left[i:] + right[j:]

def merge_sort(items):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    return merge(left, right)

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
print(merge_sort([]))
print(merge_sort(["Linus", "Ada", "Hedy", "Alan"]))

output

[3, 9, 10, 27, 38, 43, 82]
[]
['Ada', 'Alan', 'Hedy', 'Linus']

How it works

The base case is a list of 0 or 1 items. It is already sorted, so it is returned as it is. Every recursive call works on a shorter list, so the calls always reach the base case.
merge compares the first unused item of each list and takes the smaller one. Because both lists are already sorted, the result is sorted too.
<= (not <) takes from the left list when two items are equal. That keeps equal items in their original order, which makes the sort stable.
Merge sort does about n × log2(n) comparisons. For 1,000,000 items that is about 20 million, compared with about 500 billion for bubble sort.

The merge step on its own

python

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

print(merge([3, 27, 38, 43], [9, 10, 82]))

output

[3, 9, 10, 27, 38, 43, 82]

Python's own sorted() uses Timsort, which is based on merge sort and insertion sort. Use sorted() in real code.

Merge sort in Python

The program

How it works

The merge step on its own