O(n log n): Quasilinear Time
No single look at a row tells you where it belongs in sorted order, so sorting needs more than 1 pass. The general-purpose sorts in wide use, including the merge-based algorithm behind Python's sorted(), cost O(n log n). Merge sort shows where that comes from: treat each item as a sorted run of 1, then merge neighbouring runs into sorted runs twice as long, round after round. Every round touches all n items, and run length doubles each round, so after log n rounds a single run remains.
data = [52, 17, 88, 3, 41, 29, 70, 9]
runs = []
for x in data:
runs.append([x])
level = 0
while len(runs) > 1:
merged_runs = []
for i in range(0, len(runs), 2):
left = runs[i]
right = runs[i + 1]
out = []
a = 0
b = 0
while a < len(left) and b < len(right):
if left[a] <= right[b]:
out.append(left[a])
a += 1
else:
out.append(right[b])
b += 1
out = out + left[a:] + right[b:]
merged_runs.append(out)
runs = merged_runs
level += 1
print("level", level, runs)level 1 [[17, 52], [3, 88], [29, 41], [9, 70]] level 2 [[3, 17, 52, 88], [9, 29, 41, 70]] level 3 [[3, 9, 17, 29, 41, 52, 70, 88]]
The 8 values took 3 rounds of 8 moves each, 24 moves in total, and that is the whole shape of n log n: log n passes over the data.
| Rows (n) | n | n log n | n² |
|---|---|---|---|
| 1,000 | 1,000 | about 10,000 | 1,000,000 |
| 1,000,000 | 1,000,000 | about 20 million | 1 trillion |
| 1,000,000,000 | 1 billion | about 30 billion | 1 quintillion |
The middle column sits far closer to n than to n². At 1,000,000 rows a sort does about 20 passes' worth of work, while comparing every pair does 1,000,000 passes' worth, which is why a nightly sort of a billion rows is routine and an all-pairs comparison of the same rows never finishes.
Window functions sort inside each partition
SQL ranks rows within groups through a window function. The query below numbers each user's tracks from most played to least: PARTITION BY user_id splits the rows into 1 group per user, ORDER BY play_count DESC sorts each group, and ROW_NUMBER() counts 1, 2, 3 down each sorted group.
SELECT
user_id,
track_id,
ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY play_count DESC) AS track_rank
FROM user_track_counts- user_track_counts (source, n rows in)
- Group by user_id (transform, 1 pass, O(n))
- Sort each group (transform, k log k per group)
- Number rows (transform, 1 pass, O(n))
- Ranked tracks (consumer, n rows out)
- user_track_counts -> Group by user_id
- Group by user_id -> Sort each group
- Sort each group -> Number rows
- Number rows -> Ranked tracks
A group of k rows costs about k log k to sort, so the window's total is that cost summed over the groups. Smaller groups shrink the log: sorting 1,000 groups of 1,000 rows pays about 10 per row, while a window with no PARTITION BY sorts the whole table as a single group and pays log n per row.
import math
def sort_cost(n):
if n < 2:
return 0
return n * math.log2(n)
one_sort = sort_cost(1_000_000)
per_user = 1_000 * sort_cost(1_000)
print(f"one global sort: {one_sort:,.0f}")
print(f"1,000 sorts of 1,000: {per_user:,.0f}")Output:
one global sort: 19,931,569 1,000 sorts of 1,000: 9,965,784
Partitioning by user halved the predicted work, because log 1,000 is half of log 1,000,000.
A nightly job sorts 2 million rows in 4 seconds. Next quarter the table holds 4 million rows. About how long should the sort take?
- About 16 seconds, because doubling the rows quadruples a sort
- About 4 seconds, because the log factor keeps sorting flat
- Exactly 8 seconds, because sorting grows in step with row count
- A little over 8 seconds: twice the rows, plus 1 more merge round
Sorting each group in Python
Python code ranks within groups the same way: keep a dict that maps each user_id to a list of that user's rows, and sort each list on its own. The cost follows the SQL window, about k log k per list of k rows, added up across users. sorted() calls its key function once per item before it compares anything, so a key that reads 1 field adds n calls to the sort, far fewer than its n log n comparisons. reverse=True puts the largest key first, the job DESC does inside the window.
sales_by_region = {
"north": [("n1", 120), ("n2", 340), ("n3", 90)],
"south": [("s1", 75), ("s2", 410)],
}
def by_amount(sale):
return sale[1]
for region, sales in sales_by_region.items():
ranked = sorted(sales, key=by_amount, reverse=True)
print(region, ranked[0][0])About this lesson
This section is part of the Complexity: Intermediate 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.