Python programs / Searching and sorting / Merge sort

Python Program for Merge Sort

Intermediate Searching and sorting Time O(n log n) Space O(n)

Sorts a list by splitting it in half, sorting each half the same way, then merging the two sorted halves into one.

Merge sort is a divide and conquer algorithm: it breaks the list into smaller lists until each has one item, which is sorted already, so all the real work is in merging. Two sorted lists combine into one by taking the smaller of their front items again and again. Merging [27, 38, 43] and [3, 9, 10, 82] takes 3, 9 and 10 from the right, then 27, 38 and 43 from the left, then the 82 that's left over.

Program

def merge_sort(items):
    """Return the items sorted from smallest to largest."""
    if len(items) <= 1:
        return items
    middle = len(items) // 2
    left = merge_sort(items[:middle])
    right = merge_sort(items[middle:])
    return merge(left, right)


def merge(left, right):
    """Merge two sorted lists into one sorted list."""
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    # One list is used up: the rest of the other is already sorted
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged


numbers = [38, 27, 43, 3, 9, 82, 10]
print("Before:", numbers)
print("After: ", merge_sort(numbers))

Open in the editor Download merge_sort.py

Output

Before: [38, 27, 43, 3, 9, 82, 10]
After:  [3, 9, 10, 27, 38, 43, 82]

How it works

  1. A list of one item, or none, is already sorted, so the function returns it as it is. This is the base case that stops the recursion.
  2. middle is the index where the list splits: 7 items split into 3 and 4.
  3. The function calls itself to sort each half. Slicing makes new lists, so the list it was given is never changed.
  4. The two sorted halves are merged into one sorted list, which is returned.
  5. merge builds a new list, merged. i and j point at the first item of left and of right that hasn't been taken yet.
  6. While both lists have items left, the smaller of their two front items goes onto merged, and that list's pointer moves on. On a tie, <= takes the item from left, which keeps equal items in their original order.
  7. Once one list is used up, the rest of the other is sorted and no smaller than anything in merged, so extend() adds it at the end. One of the two slices is empty.
  8. The program prints the list, then the sorted list that merge_sort returns.

The list is split until every piece has one item, then the pieces are merged back together in this order:

Merge left right merged
1 [27] [43] [27, 43]
2 [38] [27, 43] [27, 38, 43]
3 [3] [9] [3, 9]
4 [82] [10] [10, 82]
5 [3, 9] [10, 82] [3, 9, 10, 82]
6 [27, 38, 43] [3, 9, 10, 82] [3, 9, 10, 27, 38, 43, 82]

Time and space complexity

TimeO(n log n)
Extra spaceO(n)

Halving the list again and again reaches pieces of one item after about log₂ n levels: 3 for 7 items, 20 for a million. At each level the merges together handle every item once, which is O(n) work, so the whole sort takes O(n log n) time. That holds for every list, sorted, reversed or mixed, so the best, average and worst cases are the same. The merged lists and the slices need O(n) extra space, more than the O(1) of the simpler sorts, and the calls go about log₂ n deep. Merge sort is stable. Python's own sorted() uses Timsort, a merge sort that first looks for stretches of the list that are already in order.

Other ways to write it

Sorting the list in place

Many textbooks write merge sort to change the list it's given, as list.sort() does. The halves are still copies, but the merge writes back into items.

def merge_sort(items):
    if len(items) <= 1:
        return
    middle = len(items) // 2
    left, right = items[:middle], items[middle:]
    merge_sort(left)
    merge_sort(right)
    i = j = k = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            items[k] = left[i]
            i += 1
        else:
            items[k] = right[j]
            j += 1
        k += 1
    items[k:] = left[i:] + right[j:]  # whatever is left over

numbers = [38, 27, 43, 3, 9, 82, 10]
merge_sort(numbers)
print(numbers)

With heapq.merge()

The standard library's heapq.merge() merges sorted lists, so only the splitting is left to write (modules).

from heapq import merge

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

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

Try it yourself

  • Print left, right and merged at the end of merge, and compare them with the table above.
  • Sort a list of 8 items, a list of one item and an empty list.
  • Sort from largest to smallest by changing one comparison in merge.
  • Sort words by length, comparing len(left[i]) <= len(right[j]), and check that words of the same length keep their order: that's what stable means.

More searching and sorting programs

Share this program