Merge Sort

Divide the list into single items, then merge them back in order.

A merge sort uses a 'divide and conquer' approach. It splits the list in half again and again until every piece holds a single item, then merges those pieces back together in order. It is more complex than bubble or insertion sort, but far faster on large lists.

Stage 1: divide

First the list is split in half repeatedly until every sublist holds just one item. A single item is, on its own, already sorted.

split once

4231123

37182947

split again

4231

123

3718

2947

down to single items

Stage 2: merge

Now pairs of sublists are merged back together. Each merge combines two already-sorted lists into one sorted list. This repeats until a single sorted list remains.

merge into sorted pairs

3142

312

1837

2947

merge again

3123142

18293747

final merge — fully sorted

312182931374247

Merging two sorted lists

The heart of a merge sort is combining two sorted lists into one. Look at the front of each list, take the smaller of the two, and repeat until both lists are empty.

merge.py

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

print(merge([31, 42], [3, 12]))
print(merge([18, 37], [29, 47]))

Output

[3, 12, 31, 42]
[18, 29, 37, 47]

How it works

i and j mark the front of left and right.
The first loop compares the two fronts and appends the smaller, then moves that marker on.
When one list runs out, the two short loops copy any items left over — already in order.
result ends up holding every item in sorted order.

Merge sort in Python

To sort a whole list, merge sort splits it in half, sorts each half, then merges the two sorted halves. Each half is sorted the very same way, on smaller and smaller lists, until every piece holds one item.

mergesort.py

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)

data = [42, 31, 12, 3, 37, 18, 29, 47]
print(merge_sort(data))

Output

[3, 12, 18, 29, 31, 37, 42, 47]

How it works

If a list has 0 or 1 items it is already sorted, so it is returned unchanged — this stops the splitting.
Otherwise mid = len(items) // 2 finds the middle, and items[:mid] / items[mid:] are the two halves.
Each half is sorted by merge_sort itself, then merge() combines them in order.

Recursion: a function that calls itselfmerge_sort calls itself on each half. A function that calls itself is using recursion — a more advanced idea you will meet again later. The split diagram above shows exactly what those calls do: keep halving until each piece is a single item, then merge back up.

Comparing the three sorts

All three algorithms put a list in order, but they differ in speed and complexity.

	Bubble sort	Insertion sort	Merge sort
How it works	Swap neighbouring pairs over many passes	Insert each item into a sorted front	Split into single items, then merge in order
Ease	Easiest to follow	Fairly easy	Most complex
Speed on large lists	Slow	Slow	Fast
Best for	Tiny or nearly-sorted lists	Small or nearly-sorted lists	Large lists

The trade-offBubble and insertion sorts are simple but get slow quickly as a list grows. Merge sort is much faster on large lists because it halves the work each time, but it is more complex and uses extra memory to hold the sublists.

What you have learned

A merge sort splits the list into single items (divide), then merges sorted sublists back together (conquer).
Merging combines two sorted lists by repeatedly taking the smaller front item.
A single item is already sorted, which is where the splitting stops.
Merge sort is more complex than bubble or insertion sort, but much faster on large lists.