Asking About Scale Before Sorting

Every solution so far assumed the rows already sit in a Python list. In a data engineering interview, the strongest first move after hearing a sorting prompt is a question: how many rows, and how big is each one? The answer decides whether sorted() is the whole solution, whether the sort belongs in the query engine, or whether the data has to be sorted in pieces.

What a row costs in memory

Every Python object carries a header, so a row costs several times its raw bytes. Take one play record stored as a tuple, ('user_123456', 4821, 3.75). As a CSV line, user_123456,4821,3.75 plus its newline, it is 22 bytes. On 64-bit CPython 3.9, sys.getsizeof reports these sizes for its parts:

Object	Bytes
tuple of 3 references	64
str 'user_123456'	60
int 4821	28
float 3.75	24
list slot pointing at the tuple	8
Total per row	184

import sys

row = ('user_123456', 4821, 3.75)
parts = [sys.getsizeof(row)] + [sys.getsizeof(v) for v in row]
print(parts)
print(sum(parts) + 8)

On 64-bit CPython 3.9 this prints [64, 60, 28, 24] and then 184, the 8 being the list slot. The row costs about 8 times its CSV size. At 10,000,000 rows that comes to 1.84 GB before any sorting starts, and sorted() then adds a second list of references, another 80 MB. A tuple key adds a freshly built tuple per row for the duration of the sort, and Timsort's merge step borrows temporary space of up to half the list's references.

5.4M
21 GB

The in-memory boundary

A working rule: sort in memory when the estimate, plus the copy and the keys, stays well under the RAM the process may use. Keep roughly half in reserve, because the interpreter and the rest of the program need memory too. Past that line, one sorted() call either fails with MemoryError or pushes the machine into swap, where every page fault waits on the disk and the job's runtime grows by orders of magnitude.

Situation	Approach
Fits in RAM with room to spare	sorted() or .sort() inside the process
Rows live in a table a query engine can read	ORDER BY in the query, receive sorted rows
Only the top K rows matter	A heap of size K, covered in the next section
Too large for RAM and full order required	External merge sort: sorted runs, then a k-way merge

Pushing the sort to the query engine

When the rows already sit in a table, the cheapest sort is often the one Python never runs. A query engine sorts across many workers and spills to disk on its own, and with a LIMIT it can keep only the top rows instead of ordering everything.

SELECT
  track,
  artist,
  streams
FROM weekly_plays
WHERE week_start = DATE '2024-03-04'
ORDER BY streams DESC, track ASC
LIMIT 10

External sort in one picture

When the full order is required and the data exceeds RAM, the standard answer is an external merge sort. Read a chunk that fits in memory, sort it, and write it out as a sorted run. Repeat until the input is consumed. Then merge: hold the smallest unread row of each run, emit the smallest of those, and refill from the run it came from. Memory during the merge is one row per run, whatever the total size.

A 200 GB CSV cut into 250 MB chunks, each about 2 GB once loaded as Python tuples, yields 800 sorted runs; the merge reads all 800 together, 1 row from each at a time.

Unsorted input (source, 200 GB of CSV rows)
Chunk sorter (transform, sorted() per 250 MB CSV chunk); parallelism: 800 chunks
Sorted runs (storage, 800 run files)
K-way merge (transform, heapq.merge)
Sorted output (consumer, one ordered stream)

Unsorted input -> Chunk sorter
Chunk sorter -> Sorted runs
Sorted runs -> K-way merge
K-way merge -> Sorted output

The merge step already exists in the standard library. heapq.merge takes any number of sorted iterables and yields one sorted stream, reading lazily and holding a single element from each input. It accepts the same key= and reverse= arguments as sorted().

import heapq

run_a = [3, 9, 14]
run_b = [1, 10, 12]
run_c = [5, 6, 20]

merged = heapq.merge(run_a, run_b, run_c)
print(list(merged))

This prints [1, 3, 5, 6, 9, 10, 12, 14, 20]. In a real external sort each run would be read row by row from storage, and the list call at the end would be replaced by writing each row out as it is produced.

Building the full external sort, with run files and a hand-written k-way heap merge, is the subject of a later lesson in this track.

About this lesson

This section is part of the Custom Sorting: Beginner lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.