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)nn log nn²
1,0001,000about 10,0001,000,000
1,000,0001,000,000about 20 million1 trillion
1,000,000,0001 billionabout 30 billion1 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
Rows move left to right; only the sort step grows faster than the row count.
  • 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?

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.