Master

Sorting data that does not fit

When the data is bigger than memory, sort it in chunks and merge the sorted chunks. This is external sorting, and it is how big files get ordered.

What you will see

About 3 min of reading

Try It

Sort in chunks and merge them.

Sort chunks of two.

nums = [9, 1, 7, 3, 8, 2] chunk = 2 chunks = [sorted(nums[i:i + chunk]) for i in range(0, len(nums), chunk)] print(chunks)

Before you run it, say out loud what it will print. Then open the answer.

What it prints

[[1, 9], [2, 3], [7, 8]]

Merge three sorted chunks.

import heapq chunks = [[1, 9], [2, 3], [7, 8]] print(list(heapq.merge(*chunks)))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

[1, 2, 3, 7, 8, 9]

Take the first merged value.

import heapq a = iter([1, 5, 9]) b = iter([2, 3, 8]) print(next(heapq.merge(a, b)))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Rounds to merge four chunks.

import math print(math.ceil(math.log2(4)))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Put it in order

Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.

Data Flow

Data larger than memory sorts in chunks that fit, then merges the sorted chunks with a streaming merge, keeping cost near n log n.

1 split into chunks

↓

2 sort each chunk

↓

3 merge sorted chunks

↓

4 one ordered stream

Line by line

Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.

nums = [9, 1, 7, 3, 8, 2] sets nothing on screen

chunk = 2 sets nothing on screen

chunks = [sorted(nums[i:i + chunk]) for i in range(0, len(nums), chunk)] sets nothing on screen

print(chunks) [[1, 9], [2, 3], [7, 8]]

Why this works

External sort is the pattern

Sort what fits, write it out, merge the sorted pieces. The same merge that powers merge sort now works across files.

Read once if you can

If a single pass plus a small amount of state is enough, avoid sorting at all. Counting or bucketing can order data without comparisons.

Examples

Split into chunks

nums = [9, 1, 7, 3, 8, 2]
chunk = 2
chunks = [sorted(nums[i:i + chunk]) for i in range(0, len(nums), chunk)]
print(chunks)

Sort each chunk to fit memory. Now you hold several sorted rows instead of one big unsorted one.

Merge two sorted chunks

left = [1, 9]
right = [2, 3]
out = []
i = j = 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
out += left[i:] + right[j:]
print(out)

Merging two sorted chunks gives one sorted chunk. Repeat until one row is left.

Merge all chunks

import heapq
chunks = [[1, 9], [2, 3], [7, 8]]
print(list(heapq.merge(*chunks)))

heapq.merge k sorted rows at once. It reads the fronts and yields the smallest, without loading everything.

Write sorted chunks out

nums = [9, 1, 7, 3]
chunk = 2
parts = [sorted(nums[i:i + chunk]) for i in range(0, len(nums), chunk)]
print(parts)

Each sorted chunk goes to its own file. The merge step reads the files back one item at a time.

Cost stays n log n

import math
print(round(1000 * math.log2(1000)))

Sorting chunks then merging them is still about n log n. The extra cost is reading the data more than once.

Streaming merge

import heapq
a = iter([1, 5, 9])
b = iter([2, 3, 8])
print(next(heapq.merge(a, b)))

The merge yields one value at a time. Memory stays small no matter how long the rows are.

Count the passes

import math
print(math.ceil(math.log2(4)))

Four chunks merge in two rounds of pairing. The number of rounds is the log of the chunk count.

Pick chunk size

print(1000 * 1000)

Chunks are as big as memory allows. Bigger chunks mean fewer files and fewer merge rounds.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← Sorting records by several keys

Previous Lesson

Sorting records by several keys

Next Lesson

A comparator of your own

A comparator of your own →