EngineersofAI LogoCoursesBlogResearch LabAI LettersThe LabCode BankInteractive 3DKodrEarnestJobs
Skip to main content

Sorting Mechanisms - Timsort and Python's Sort Guarantee

Reading time: ~18 minutes | Level: Foundation → Engineering

Here is a question that reveals whether you understand Python sorting at the engineering level.

data = [
    {"name": "Alice", "score": 90, "joined": 1},
    {"name": "Bob",   "score": 90, "joined": 2},
    {"name": "Carol", "score": 85, "joined": 3},
]

# Sort by score descending
result = sorted(data, key=lambda x: x["score"], reverse=True)
for r in result:
    print(r["name"], r["score"])

Output:

Alice 90
Bob   90
Carol 85

Now the question: is it guaranteed that Alice always comes before Bob? They have the same score. Does the sort preserve their original relative order?

The answer is yes - and this is not an accident. Python's sort is guaranteed stable by the language specification. Understanding why, and what algorithm achieves this, separates engineers from syntax-users.

What You Will Learn​

  • How Timsort works: the merge sort + insertion sort hybrid designed for real-world data
  • Why Timsort outperforms pure merge sort on partially-sorted sequences
  • The precise difference between sort() and sorted() - in-place vs new object
  • What sort stability means and why it matters for multi-pass ranking systems
  • How natural ordering works for integers, strings, and tuples
  • How to sort in descending order and handle mixed-type edge cases
  • Multi-key sorting using tuple keys - the canonical Python pattern
  • The Schwartzian transform (decorate-sort-undecorate) and when to use it
  • Memory and performance characteristics for production-scale data

Prerequisites​

  • Python lists, tuples, dicts (Module 4, Lessons 1–4)
  • Lambda functions and basic callable syntax
  • Time Complexity fundamentals (Lesson 9 of this module)

Part 1 - Timsort: The Algorithm Behind Python's Sort​

Python uses Timsort, designed by Tim Peters in 2002 specifically for Python. It was later adopted by Java (Java 7+), Android, and V8. It is considered one of the best general-purpose sorting algorithms for real-world data.

Why Not Pure Merge Sort?​

Pure merge sort is theoretically optimal: O(n log n) worst case, stable. But it has weaknesses:

  • It ignores existing order in the data - it sorts everything from scratch
  • It always takes O(n log n) even if data is already 90% sorted
  • It has high overhead for small arrays

Why Not Pure Insertion Sort?​

Insertion sort is excellent for small arrays (cache-friendly, low overhead) and for nearly-sorted data (O(n) best case). But it degrades to O(n²) for large, random data.

Timsort: The Best of Both​

Timsort exploits the fact that real-world data is rarely fully random. Logs have chronological clustering. Databases have indexed fields. Sensor readings have local monotonicity. Financial data has trends.

Given [5, 3, 1, 2, 4, 8, 7, 9, 6, 10, 11, 12, 13, ...]:

  1. Scan for runs (already-sorted sequences): [1,3,5] · [2,4,7,8] · [6,9,10,...]
  2. Extend short runs (< minrun ≈ 32–64 elements) using insertion sort
  3. Merge adjacent runs using merge sort: Run1+Run2 → [1,2,3,4,5,7,8] → merged with Run3 → final sorted output

Result: O(n) for already-sorted data, O(n log n) worst case.

Run Detection​

# Timsort detects ascending and descending runs
# Descending runs are reversed in-place (O(k) for k elements)

data = [5, 4, 3, 2, 1, 2, 3, 4, 5]
#        ↑─────────────↑             descending run: [5,4,3,2,1]
#                        ↑─────────↑ ascending run:  [2,3,4,5]
# Timsort reverses the first run: [1,2,3,4,5] then merges

data.sort()
print(data)   # [1, 2, 2, 3, 3, 4, 4, 5, 5]

Timsort Performance Characteristics​

CaseComplexityExample
Already sortedO(n)Timestamps in append order
Reverse sortedO(n)Reversed logs (reversed in-place)
Random dataO(n log n)Hash outputs, random sampling
Multiple sorted chunksO(n log k)k = number of chunks, k ≪ n
Single elementO(1)len(data) == 1
Empty listO(1)len(data) == 0
Worst case (guaranteed)O(n log n)
Average caseO(n log n)
import time
import random

def benchmark_sort(data, label):
    copy = data[:]
    start = time.perf_counter()
    copy.sort()
    elapsed = time.perf_counter() - start
    print(f"{label:30s}: {elapsed:.4f}s")

n = 1_000_000

random_data     = [random.randint(0, n) for _ in range(n)]
sorted_data     = list(range(n))
reverse_data    = list(range(n, 0, -1))
nearly_sorted   = sorted_data[:]
# Shuffle only 1% of elements
for _ in range(n // 100):
    i, j = random.randrange(n), random.randrange(n)
    nearly_sorted[i], nearly_sorted[j] = nearly_sorted[j], nearly_sorted[i]

benchmark_sort(random_data,   "Random data")
benchmark_sort(sorted_data,   "Already sorted")
benchmark_sort(reverse_data,  "Reverse sorted")
benchmark_sort(nearly_sorted, "Nearly sorted (1% shuffled)")

Output (approximate):

Random data                   : 0.1821s
Already sorted                : 0.0312s   ← 5.8x faster
Reverse sorted                : 0.0289s   ← 6.3x faster
Nearly sorted (1% shuffled)   : 0.0401s   ← 4.5x faster

:::tip Why Timsort Matters for Real-World Systems Real-world data is almost never uniformly random. Log files, database query results, sensor streams, and financial data all contain partially-sorted sequences. Timsort exploits this structure, which is why Python's sort often runs much faster in practice than the theoretical O(n log n) worst case suggests. :::

Part 2 - sort() vs sorted(): In-Place vs New Object​

These two functions sort by the same algorithm, but differ in crucial ways.

original = [3, 1, 4, 1, 5, 9, 2, 6]

# list.sort() - modifies in place, returns None
result = original.sort()
print(result)     # None  ← common gotcha!
print(original)   # [1, 1, 2, 3, 4, 5, 6, 9]

original = [3, 1, 4, 1, 5, 9, 2, 6]

# sorted() - returns new list, original unchanged
result = sorted(original)
print(result)     # [1, 1, 2, 3, 4, 5, 6, 9]
print(original)   # [3, 1, 4, 1, 5, 9, 2, 6]  ← unchanged

:::danger Common Bug: my_list = my_list.sort() list.sort() returns None. Writing data = data.sort() sets data to None, destroying your reference to the list. This is a frequent Python bug. Use data.sort() (no assignment) for in-place sort, or data = sorted(data) for a new sorted copy. :::

When to Use Each​

Use list.sort() whenUse sorted() when
You own the list and can mutate itYou need to preserve the original
Memory efficiency matters (large n)Sorting non-list iterables (tuples, generators, sets, dicts)
You don't need the original orderYou want to sort and assign in one step
Chaining sort with other opsSorting inside expressions/comprehensions
# sorted() works on any iterable, not just lists
my_tuple = (3, 1, 4, 1, 5)
print(sorted(my_tuple))       # [3, 1, 4, 1, 5] sorted → returns list

my_set = {5, 3, 1, 4, 2}
print(sorted(my_set))         # [1, 2, 3, 4, 5]  → returns list

my_dict = {"c": 3, "a": 1, "b": 2}
print(sorted(my_dict))        # ['a', 'b', 'c']  → sorts keys, returns list
print(sorted(my_dict.items(), key=lambda x: x[1]))  # sort by value
# [('a', 1), ('b', 2), ('c', 3)]

# Generator - sorted() materializes it
def gen():
    yield 5; yield 3; yield 1

print(sorted(gen()))   # [1, 3, 5]

Memory Comparison​

import sys
import tracemalloc

data = list(range(1_000_000))

# list.sort(): O(1) extra memory (sorts in place)
tracemalloc.start()
data.sort()
current, peak = tracemalloc.get_traced_memory()
tracemalloc.stop()
print(f"list.sort() peak extra memory: {peak / 1024 / 1024:.1f} MB")
# list.sort() peak extra memory: 0.0 MB  (in-place, no copy)

# sorted(): O(n) extra memory (new list)
tracemalloc.start()
new_list = sorted(data)
current, peak = tracemalloc.get_traced_memory()
tracemalloc.stop()
print(f"sorted() peak extra memory:    {peak / 1024 / 1024:.1f} MB")
# sorted() peak extra memory:    7.6 MB  (new list of 1M pointers)

For 10 million elements, sorted() temporarily requires ~76 MB of additional memory for the new list. On memory-constrained systems, always prefer list.sort().

Part 3 - Sort Stability: The Engineering Guarantee​

Python's sort is guaranteed stable: if two elements compare as equal, they appear in the result in the same relative order as in the input. This is not just an implementation detail - it is part of the Python language specification.

Why Stability Matters: Multi-Pass Sorting​

Stability enables a powerful technique: sort by secondary key first, then by primary key. The final result is correctly ordered by primary key with secondary key as tiebreaker.

employees = [
    {"name": "Alice",   "dept": "Engineering", "salary": 95000},
    {"name": "Bob",     "dept": "Marketing",   "salary": 80000},
    {"name": "Carol",   "dept": "Engineering", "salary": 110000},
    {"name": "Dave",    "dept": "Marketing",   "salary": 80000},
    {"name": "Eve",     "dept": "Engineering", "salary": 95000},
]

# Goal: sort by dept (ascending), then by salary (descending within dept)

# Multi-pass approach - works because sort is stable:
# Step 1: Sort by salary descending
employees.sort(key=lambda e: e["salary"], reverse=True)
# Step 2: Sort by dept ascending - stable sort preserves salary order within depts
employees.sort(key=lambda e: e["dept"])

for e in employees:
    print(f"{e['dept']:15} {e['name']:8} ${e['salary']:,}")

Output:

Engineering     Carol    $110,000
Engineering     Alice    $95,000
Engineering     Eve      $95,000
Marketing       Bob      $80,000
Marketing       Dave     $80,000

Carol (highest salary in Engineering) comes first within her department. Bob and Dave (equal salary in Marketing) maintain their original relative order. This works only because Python's sort is stable.

:::note The Equivalent Single-Pass Approach The multi-pass trick is equivalent to using a tuple key in a single sort. Both rely on stability, but the tuple approach (covered in Part 6) is more concise and performs one sort instead of two. :::

Part 4 - Natural Ordering: How Types Compare​

Python's sort uses __lt__ (less-than) by default. Understanding natural ordering prevents type errors.

Integers: Numeric Order​

nums = [5, -3, 0, 100, -1]
nums.sort()
print(nums)   # [-3, -1, 0, 5, 100]

# Floats sort by value
floats = [3.14, 2.71, 1.41, 1.73]
floats.sort()
print(floats)   # [1.41, 1.73, 2.71, 3.14]

Strings: Lexicographic (Unicode Code Point) Order​

words = ["banana", "apple", "Cherry", "date"]
words.sort()
print(words)   # ['Cherry', 'apple', 'banana', 'date']

Surprise: "Cherry" sorts before "apple" because uppercase letters have lower Unicode code points (65-90) than lowercase (97-122). This is rarely what you want.

# Case-insensitive sort
words = ["banana", "apple", "Cherry", "date"]
words.sort(key=str.lower)
print(words)   # ['apple', 'banana', 'Cherry', 'date']

Tuples: Lexicographic (Element by Element)​

data = [(2, "b"), (1, "z"), (1, "a"), (2, "a")]
data.sort()
print(data)
# [(1, 'a'), (1, 'z'), (2, 'a'), (2, 'b')]
# First by element 0, ties broken by element 1

Mixed Types: TypeError in Python 3​

# Python 3: cannot compare different types without a key function
data = [3, "hello", 1, "world"]
data.sort()   # TypeError: '<' not supported between instances of 'str' and 'int'

# Also, sorting a list containing None raises TypeError
data = [3, None, 1, None, 2]
data.sort()   # TypeError: '<' not supported between instances of 'NoneType' and 'int'

:::warning Python 2 vs Python 3: None Sorting In Python 2, None was always sorted before other values (it had a total ordering). In Python 3, comparing None to any other type raises TypeError. Production code that may receive None values must handle this explicitly - see the sorting-with-None pattern in the next lesson. :::

Part 5 - Reverse Sorting​

The reverse=True parameter reverses the sort order without changing complexity.

nums = [3, 1, 4, 1, 5, 9, 2, 6]

# Ascending (default)
print(sorted(nums))                  # [1, 1, 2, 3, 4, 5, 6, 9]

# Descending
print(sorted(nums, reverse=True))    # [9, 6, 5, 4, 3, 2, 1, 1]

# Alternative: reverse + sort (two O(n) passes)
copy = nums[:]
copy.sort()
copy.reverse()
print(copy)   # [9, 6, 5, 4, 3, 2, 1, 1]  - same result, less efficient

reverse=True still maintains stability within equal elements - reversed stability:

data = [("Alice", 90), ("Bob", 90), ("Carol", 85)]
# With reverse=True, stability means Bob stays before Alice (reversed original order)
result = sorted(data, key=lambda x: x[1], reverse=True)
print(result)
# [('Alice', 90), ('Bob', 90), ('Carol', 85)]
# Alice still before Bob - reverse=True reverses the entire order,
# but among equal elements, their reversed relative order is preserved

Actually, Python maintains stability even with reverse=True. Equal elements keep their original relative order:

data = [("Alice", 90), ("Bob", 90)]
result = sorted(data, key=lambda x: x[1], reverse=True)
# [('Alice', 90), ('Bob', 90)] - Alice before Bob even in reverse sort

Part 6 - Multi-Key Sorting with Tuple Keys​

The canonical Python pattern for sorting by multiple criteria is a tuple key. Python compares tuples lexicographically - first by element 0, then by element 1 if equal, and so on.

students = [
    {"name": "Alice", "grade": "A", "score": 95},
    {"name": "Bob",   "grade": "B", "score": 80},
    {"name": "Carol", "grade": "A", "score": 88},
    {"name": "Dave",  "grade": "B", "score": 80},
    {"name": "Eve",   "grade": "A", "score": 95},
]

# Sort by grade ascending, then score descending, then name ascending
result = sorted(
    students,
    key=lambda s: (s["grade"], -s["score"], s["name"])
)

for r in result:
    print(f"{r['grade']}  {r['score']:3d}  {r['name']}")

Output:

A   95  Alice
A   95  Eve
A   88  Carol
B   80  Bob
B   80  Dave

How the tuple key works:

  • s["grade"]: primary sort - alphabetical ("A" before "B")
  • -s["score"]: secondary sort - negated so descending (95 before 88)
  • s["name"]: tertiary sort - alphabetical for ties (Alice before Eve at score=95)

:::tip Negating Numeric Keys for Descending Sort For numeric keys, negate the value (-x["score"]) to sort that field in descending order while keeping other fields ascending. This works for integers and floats. For non-numeric types, you cannot negate - use the multi-pass approach with stable sort instead. :::

Part 7 - The Schwartzian Transform​

The Schwartzian transform (decorate-sort-undecorate) is a pattern for sorting where the key computation is expensive and should not be repeated.

import os

# Sorting files by their size - os.path.getsize() hits the filesystem each call
# If key function is called repeatedly, this is expensive

filenames = ["file_a.txt", "file_b.txt", "file_c.txt"]

# Naive: key function called once per element for comparison (this is fine in Python)
# BUT if the function has side effects or expensive I/O:
sorted_files = sorted(filenames, key=os.path.getsize)  # getsize called once per file

# Schwartzian transform: explicit decorate-sort-undecorate
# Step 1: Decorate - compute key once, cache as tuple
decorated = [(os.path.getsize(f), f) for f in filenames]
# Step 2: Sort by the cached key
decorated.sort()
# Step 3: Undecorate - extract original values
result = [f for _, f in decorated]

# Both approaches call the key function n times - same complexity
# But the transform makes caching explicit and works with any sort

A more compelling real-world example:

import hashlib

# Expensive key: SHA-256 hash of file contents
def file_hash(path):
    with open(path, "rb") as f:
        return hashlib.sha256(f.read()).hexdigest()

files = ["large_file_1.dat", "large_file_2.dat", "large_file_3.dat"]

# Schwartzian transform - read each file exactly once
decorated = [(file_hash(f), f) for f in files]   # O(n) reads
decorated.sort()                                   # O(n log n) string comparisons
sorted_files = [f for _, f in decorated]          # O(n) unpack

# Without transform, if sort calls key function multiple times (not CPython's behavior
# but true in some frameworks), you'd read each file O(log n) times instead of once

:::note Python Already Caches Key Values In CPython's implementation, sorted() and list.sort() call the key function exactly once per element and cache the results. You do not need the Schwartzian transform for pure performance in Python - the sorting machinery handles caching automatically. The transform is useful for clarity, external frameworks, or when you need the decorated list itself. :::

Part 8 - Performance Deep Dive​

Complexity Summary​

OperationComplexityMemoryNotes
list.sort()O(n log n)O(1) extraIn-place, Timsort
sorted(lst)O(n log n)O(n) extraNew list, Timsort
sorted(gen)O(n log n)O(n)Materializes generator
Already sortedO(n)O(1)Timsort run detection
Reverse sortedO(n)O(1)Timsort detects + reverses
Nearly sortedO(n log k)O(1)k = number of unsorted runs

Key Function is Called Once Per Element​

# Verification: key function call count
call_count = 0

def counted_key(x):
    global call_count
    call_count += 1
    return x["score"]

data = [{"name": f"User{i}", "score": i} for i in range(1000)]
call_count = 0
sorted_data = sorted(data, key=counted_key)

print(f"Elements: {len(data)}")
print(f"Key function calls: {call_count}")
print(f"Ratio: {call_count / len(data):.2f} (exactly 1.0)")

Output:

Elements: 1000
Key function calls: 1000
Ratio: 1.00 (exactly 1.0)

The key function is called exactly once per element - O(n) key calls total, then O(n log n) comparisons on the cached keys.

Comparison: sort() for Large Data​

import time
import random

def benchmark(n, label):
    data = [random.randint(0, n * 10) for _ in range(n)]

    # In-place sort
    copy_a = data[:]
    start = time.perf_counter()
    copy_a.sort()
    inplace_time = time.perf_counter() - start

    # New list sort
    copy_b = data[:]
    start = time.perf_counter()
    result = sorted(copy_b)
    newlist_time = time.perf_counter() - start

    print(f"n={n:>8,}  sort(): {inplace_time:.3f}s  sorted(): {newlist_time:.3f}s")

benchmark(100_000)
benchmark(1_000_000)
benchmark(10_000_000)

Output (approximate):

n=   100,000  sort(): 0.008s  sorted(): 0.008s
n= 1,000,000  sort(): 0.098s  sorted(): 0.101s
n=10,000,000  sort(): 1.124s  sorted(): 1.178s

Both run at approximately the same speed for the sort itself. The difference is memory: sorted() allocates an extra O(n) list, which matters at large n.

Part 9 - Edge Cases and Production Gotchas​

Sorting None Values​

# Python 3: raises TypeError
data = [3, None, 1, None, 2]
data.sort()   # TypeError: '<' not supported between 'NoneType' and 'int'

# Fix 1: filter out None before sorting
clean = sorted(x for x in data if x is not None)
print(clean)   # [1, 2, 3]

# Fix 2: sort None to the end
data = [3, None, 1, None, 2]
data.sort(key=lambda x: (x is None, x if x is not None else 0))
print(data)   # [1, 2, 3, None, None]

# Fix 3: sort None to the front
data = [3, None, 1, None, 2]
data.sort(key=lambda x: (x is not None, x if x is not None else 0))
print(data)   # [None, None, 1, 2, 3]

Sorting Heterogeneous Types​

# Python 3 does not support comparison across different types
data = [3, "hello", 1, "world"]
sorted(data)   # TypeError!

# Fix: convert to a common type or use a key that normalizes
data = [3, "hello", 1, "world"]
result = sorted(data, key=str)
print(result)   # [1, 3, 'hello', 'world']  (sorted by string representation)

The Gotcha: sort() Returns None​

# Classic Python gotcha that causes subtle bugs
names = ["Charlie", "Alice", "Bob"]

# WRONG - assigns None to names
names = names.sort()
print(names)   # None  ← list is lost!

# CORRECT - sort in place (no assignment)
names = ["Charlie", "Alice", "Bob"]
names.sort()
print(names)   # ['Alice', 'Bob', 'Charlie']

# OR use sorted() with assignment
names = ["Charlie", "Alice", "Bob"]
names = sorted(names)
print(names)   # ['Alice', 'Bob', 'Charlie']

Sorting Dicts by Value​

scores = {"Alice": 95, "Bob": 80, "Carol": 88, "Dave": 72}

# Sort by value, return sorted list of (name, score) tuples
ranked = sorted(scores.items(), key=lambda x: x[1], reverse=True)
print(ranked)
# [('Alice', 95), ('Carol', 88), ('Bob', 80), ('Dave', 72)]

# Reconstruct sorted dict (Python 3.7+ preserves insertion order)
ranked_dict = dict(ranked)
print(ranked_dict)
# {'Alice': 95, 'Carol': 88, 'Bob': 80, 'Dave': 72}

Interview Questions​

Q1: What is Timsort and why does Python use it instead of a simpler algorithm like quicksort?​

Answer: Timsort is a hybrid sorting algorithm combining merge sort (for large arrays) and insertion sort (for small arrays), designed by Tim Peters in 2002. Python uses Timsort because: (1) It guarantees O(n log n) worst case - quicksort's worst case is O(n²) on already-sorted data or adversarial input. (2) It is stable - equal elements maintain their relative order, which is critical for multi-key sorting. (3) It exploits real-world data structure: by detecting "runs" (already-sorted subsequences), it achieves O(n) on already-sorted data and O(n log k) on data with k sorted runs, far outperforming pure merge sort on the partially-sorted data that dominates real-world workloads.

Q2: What is the difference between list.sort() and sorted()? When would you choose each?​

Answer: list.sort() sorts the list in place and returns None. sorted() creates and returns a new sorted list, leaving the original unchanged. Both use Timsort - same algorithm, same O(n log n) complexity. Choose list.sort() when: you own the list, memory efficiency matters (no extra O(n) allocation), and you don't need the original order. Choose sorted() when: you need the original preserved, you're sorting non-list iterables (tuples, generators, sets), or you're sorting inside an expression. Common gotcha: data = data.sort() sets data to None - never assign the return value of list.sort().

Q3: What does "stable sort" mean, and why does it matter in Python?​

Answer: A stable sort guarantees that elements which compare as equal maintain their original relative order after sorting. Python's sort is guaranteed stable by the language specification - not just an implementation detail. This matters because it enables multi-pass sorting: sort by secondary criterion first, then by primary criterion. The stable sort preserves the secondary ordering within each group defined by the primary key. Without stability, you cannot rely on multi-pass sorting correctness. Example: sort employees by department (primary) then by salary descending (secondary). Sort salary descending first, then sort department ascending - the final result correctly shows employees sorted by department with salary-descending order within each department.

Q4: Why can't Python 3 sort a list containing both integers and strings?​

Answer: Python 3's sort uses __lt__ (less-than) to compare elements. There is no defined total ordering between int and str - 3 < "hello" has no sensible meaning and raises TypeError: '<' not supported between instances of 'int' and 'str'. Python 2 had an arbitrary (but consistent) rule for cross-type comparisons, which led to confusing results. Python 3 enforces that only types with a meaningful ordering can be compared. Fix: provide a key function that converts all elements to a comparable type (key=str, or key=lambda x: (type(x).__name__, x) for type-then-value ordering).

Q5: How does Python's sort handle reverse=True in terms of stability?​

Answer: reverse=True does not break stability. Python uses a technique that reverses the entire comparison result, then applies the stable merge-sort merging logic. Equal elements still maintain their original relative order. However, an important subtlety: with reverse=True, "original order" is maintained in the reversed sense. If Alice and Bob are equal, and Alice was at index 0 and Bob at index 1, after reverse=True sort, Alice still appears before Bob in the result (both their equal-priority slots maintain relative position). This is Python's guaranteed behavior, tested in CPython's test suite.

Q6: You have 50 million log entries. Each has a timestamp and severity. How do you efficiently sort by severity first, then timestamp within each severity level?​

Answer: Use a single sort with a tuple key:

# O(n log n) - single pass, one allocation
logs.sort(key=lambda log: (log["severity"], log["timestamp"]))

This is equivalent to two stable sorts (sort by timestamp first, then severity) but more efficient - one sort instead of two. If severity is an enum with a non-alphabetical ordering (e.g., DEBUG < INFO < WARNING < ERROR < CRITICAL), map it to an integer first:

SEVERITY_RANK = {"DEBUG": 0, "INFO": 1, "WARNING": 2, "ERROR": 3, "CRITICAL": 4}

logs.sort(key=lambda log: (SEVERITY_RANK[log["severity"]], log["timestamp"]))

For 50 million entries, the key function is called exactly 50 million times (once per element, cached by Timsort). Memory usage is O(n) for the key cache. If memory is critical, use list.sort() instead of sorted() to avoid the O(n) new list allocation.

Practice Challenges​

Beginner: Predict the Output​

What does this code print? Explain why.

data = ["banana", "Apple", "cherry", "Date"]
sorted_a = sorted(data)
sorted_b = sorted(data, key=str.lower)

print(sorted_a)
print(sorted_b)
print(sorted_a == sorted_b)
Solution

Output:

['Apple', 'Date', 'banana', 'cherry']
['Apple', 'banana', 'cherry', 'Date']
False

Explanation:

sorted_a uses default string comparison (Unicode code points). Uppercase letters (A=65, D=68) have lower code points than lowercase (a=97, b=98, c=99), so all uppercase words sort before all lowercase words - 'Apple' before 'banana'.

sorted_b uses key=str.lower - each string is compared as if it were lowercase. So 'apple' < 'banana' < 'cherry' < 'date'. The original case is preserved in the output (the key is only for comparison), but 'Date' now sorts last because 'date' > 'cherry'.

They are not equal because element order differs: ['Apple', 'Date', ...] vs ['Apple', 'banana', ...].

Intermediate: Fix the Multi-Sort Bug​

This code is supposed to sort students by grade ascending, then by score descending within each grade. But it produces wrong results. Find and fix the bug.

students = [
    {"name": "Alice", "grade": "A", "score": 88},
    {"name": "Bob",   "grade": "B", "score": 95},
    {"name": "Carol", "grade": "A", "score": 95},
    {"name": "Dave",  "grade": "B", "score": 80},
]

# Intended: grade A first, highest score within grade first
students.sort(key=lambda s: s["grade"])
students.sort(key=lambda s: -s["score"])

for s in students:
    print(s["grade"], s["score"], s["name"])
Solution

Current (wrong) output:

A 95 Carol
B 95 Bob
A 88 Alice
B 80 Dave

Bug: The sorts are in the wrong order. The last sort wins. Sorting by -score last means the final ordering is purely by score descending, losing the grade grouping.

For multi-pass stable sorting, sort by the secondary key first, then by the primary key. The stable sort preserves secondary ordering within primary groups.

Fix - approach 1: correct order for multi-pass

students.sort(key=lambda s: -s["score"])  # secondary: score descending FIRST
students.sort(key=lambda s: s["grade"])   # primary: grade ascending LAST

for s in students:
    print(s["grade"], s["score"], s["name"])

Fix - approach 2 (preferred): single sort with tuple key

students.sort(key=lambda s: (s["grade"], -s["score"]))

for s in students:
    print(s["grade"], s["score"], s["name"])

Correct output for both:

A 95 Carol
A 88 Alice
B 95 Bob
B 80 Dave

Advanced: Design a Real-Time Leaderboard Sort​

You are building a competitive programming leaderboard. Rankings are determined by:

  1. Problems solved (descending - more is better)
  2. Total penalty time (ascending - less is better, only counts for solved problems)
  3. Last submission time (ascending - earlier submission time is better for ties)
  4. Username (ascending - alphabetical for identical everything)

Design the sort function. Handle the case where penalty time is None for users who solved 0 problems (they should sort to the bottom, regardless of username).

leaderboard = [
    {"user": "alice",   "solved": 3, "penalty": 240,  "last_sub": 180},
    {"user": "bob",     "solved": 3, "penalty": 240,  "last_sub": 120},
    {"user": "carol",   "solved": 5, "penalty": 180,  "last_sub": 300},
    {"user": "dave",    "solved": 0, "penalty": None,  "last_sub": 0},
    {"user": "eve",     "solved": 3, "penalty": 200,  "last_sub": 150},
    {"user": "frank",   "solved": 0, "penalty": None,  "last_sub": 0},
]
Solution
def leaderboard_key(entry):
    """
    Returns a tuple used for comparison.
    Python compares tuples lexicographically - first element has highest priority.

    Strategy:
    - solved: descending → negate
    - penalty: ascending, but None (0 solved) sorts LAST
      → (has_solved_nothing, penalty_value)
      → (False, 240) < (True, 0) so users with solutions rank above 0-solvers
    - last_sub: ascending
    - user: ascending (string, natural order)
    """
    solved   = entry["solved"]
    penalty  = entry["penalty"]
    last_sub = entry["last_sub"]
    user     = entry["user"]

    # Users with 0 problems solved have penalty=None - sort them to the bottom
    no_solutions = (solved == 0)

    # For the penalty sort key:
    # If no_solutions=True, the (True, 0) tuple sorts after (False, any_penalty)
    # because True > False in Python (True == 1, False == 0)
    penalty_key = (no_solutions, penalty if penalty is not None else 0)

    return (
        -solved,      # descending: more solved = better = smaller key
        penalty_key,  # ascending: less penalty = better, no-solution users last
        last_sub,     # ascending: earlier = better
        user,         # ascending: alphabetical for final tiebreak
    )


leaderboard.sort(key=leaderboard_key)

print(f"{'Rank':>4}  {'User':10} {'Solved':>6} {'Penalty':>8} {'LastSub':>8}")
print("-" * 44)
for rank, entry in enumerate(leaderboard, 1):
    penalty_str = str(entry["penalty"]) if entry["penalty"] is not None else "N/A"
    print(f"{rank:>4}  {entry['user']:10} {entry['solved']:>6} {penalty_str:>8} {entry['last_sub']:>8}")

Output:

Rank  User       Solved  Penalty  LastSub
--------------------------------------------
   1  carol           5      180      300
   2  bob             3      240      120
   3  eve             3      200      150
   4  alice           3      240      180
   5  dave            0      N/A        0
   6  frank           0      N/A        0

Explanation of ranking:

  • Carol: 5 solved - clear winner
  • Bob: 3 solved, penalty 240, last_sub 120 (earlier than alice's 180, same penalty)
  • Eve: 3 solved, penalty 200 (less than bob/alice's 240) - wait, Eve should be rank 2!

Actually with correct key: eve has penalty=200 < bob/alice penalty=240, so Eve should rank higher among the 3-solved group. Let me re-verify:

carol:  (-5, (False,180), 300, "carol")  ← smallest first element wins
eve:    (-3, (False,200), 150, "eve")    ← penalty 200
bob:    (-3, (False,240), 120, "bob")    ← penalty 240
alice:  (-3, (False,240), 180, "alice")  ← penalty 240, later last_sub
dave:   (0,  (True, 0),    0,  "dave")
frank:  (0,  (True, 0),    0,  "frank")

Correct output:

Rank  User       Solved  Penalty  LastSub
--------------------------------------------
   1  carol           5      180      300
   2  eve             3      200      150
   3  bob             3      240      120
   4  alice           3      240      180
   5  dave            0      N/A        0
   6  frank           0      N/A        0

The sort key correctly handles all four criteria and the None edge case.

Quick Reference​

Featurelist.sort()sorted()
Return valueNoneNew sorted list
Modifies originalYesNo
Works on any iterableNo (list only)Yes
Memory overheadO(1)O(n)
AlgorithmTimsortTimsort
StabilityGuaranteedGuaranteed
ComplexityO(n log n)O(n log n)
Sorting PatternCode
Basic ascendingsorted(data)
Basic descendingsorted(data, reverse=True)
By fieldsorted(data, key=lambda x: x["field"])
By attributesorted(data, key=lambda x: x.attr)
Case-insensitivesorted(strings, key=str.lower)
Multi-keysorted(data, key=lambda x: (x["a"], -x["b"]))
By dict valuesorted(d.items(), key=lambda x: x[1])
Top-k (efficient)heapq.nlargest(k, data, key=...)
None values lastkey=lambda x: (x is None, x or 0)

Key Takeaways​

  • Timsort is not just O(n log n) - it is O(n) on already-sorted data and O(n log k) on data with k sorted runs; real-world data is rarely random, so Timsort often runs faster than its worst-case implies
  • Python's sort is guaranteed stable by the language specification - equal elements maintain their original relative order; this enables multi-pass sorting and multi-key ranking systems
  • list.sort() returns None - the most common Python sorting bug is data = data.sort(); use data.sort() for in-place or data = sorted(data) for a new copy
  • The key function is called exactly once per element - CPython caches key values before sorting, so key computation is O(n), not O(n log n); complex key functions are still efficient
  • Tuple keys enable multi-criterion sorting in one pass - key=lambda x: (x["primary"], -x["secondary"]) sorts by primary ascending and secondary descending simultaneously
  • sorted() creates an O(n) new list - for memory-constrained systems with large datasets, prefer list.sort() to avoid temporary memory doubling
  • Never sort inside a loop when you can sort once - sorted(data) inside an O(m) loop is O(m × n log n); sort once before the loop for O(n log n + m)
© 2026 EngineersOfAI. All rights reserved.