Python Sorting and Timsort

Sorting sounds solved the moment you learn sorted()sorted() exists. The interview value is in the details: new list vs in-place, custom ordering, and the one guarantee — stability — that turns a single built-in into a tool for multi-key sorting. Underneath it all sits Timsort, an algorithm clever enough to notice when your data is already halfway sorted.

What you’ll learn

sorted()sorted() (returns a new list) vs list.sort()list.sort() (sorts in place, returns NoneNone).
key=key= functions: sort by length, by a tuple for multi-key ordering, or descending without reverse=reverse=.
reverse=Truereverse=True and how it composes with key=key=.
Stability: what it guarantees, and why it enables multi-pass multi-key sorts.
functools.cmp_to_keyfunctools.cmp_to_key for old-style pairwise comparators.
Timsort: the hybrid merge + insertion sort that powers both functions.

`sorted()sorted()` vs `list.sort()list.sort()`

The two easiest-to-mix-up functions in Python: one returns a new list and leaves the original untouched, the other mutates in place and returns nothing at all.

sorted_vs_sort.py

nums = [5, 2, 8, 1, 9]
 
new_list = sorted(nums)   # returns a NEW sorted list -- nums is untouched
print("original untouched:", nums)
print("new sorted list:   ", new_list)
 
result = nums.sort()      # sorts nums IN PLACE, returns None
print("nums after .sort():     ", nums)
print("return value of .sort():", result)

sorted_vs_sort.py

nums = [5, 2, 8, 1, 9]
 
new_list = sorted(nums)   # returns a NEW sorted list -- nums is untouched
print("original untouched:", nums)
print("new sorted list:   ", new_list)
 
result = nums.sort()      # sorts nums IN PLACE, returns None
print("nums after .sort():     ", nums)
print("return value of .sort():", result)

Sorting with `key=key=`

key=key= takes a function applied to each element before comparing — you sort by what the key function returns, not the elements directly.

sort_by_key.py

words = ["banana", "kiwi", "apple", "fig", "cherry"]
 
by_length = sorted(words, key=len)
print("by length:          ", by_length)
 
# descending by length -- two equivalent ways
by_length_desc_a = sorted(words, key=len, reverse=True)
by_length_desc_b = sorted(words, key=lambda w: -len(w))
print("desc via reverse=:   ", by_length_desc_a)
print("desc via negation:   ", by_length_desc_b)

sort_by_key.py

words = ["banana", "kiwi", "apple", "fig", "cherry"]
 
by_length = sorted(words, key=len)
print("by length:          ", by_length)
 
# descending by length -- two equivalent ways
by_length_desc_a = sorted(words, key=len, reverse=True)
by_length_desc_b = sorted(words, key=lambda w: -len(w))
print("desc via reverse=:   ", by_length_desc_a)
print("desc via negation:   ", by_length_desc_b)

Negating the key (-len(w)-len(w)) works for numbers because sorting ascending on -x-x is the same ordering as sorting descending on xx. It doesn’t work for strings (-w-w isn’t valid) — use reverse=Truereverse=True for those.

Multi-key sorting with a tuple

The single most useful key=key= trick: return a tuple. Python compares tuples element-by-element, so (primary, secondary)(primary, secondary) sorts by primaryprimary first and only looks at secondarysecondary to break ties.

multi_key_tuple.py

people = [
    ("Bob", 25),
    ("Amy", 30),
    ("Cid", 25),
    ("Amy", 22),
]
 
# sort by age ascending, then by name ascending for ties
by_age_then_name = sorted(people, key=lambda p: (p[1], p[0]))
print(by_age_then_name)
 
# sort by age ascending, but name descending for ties -- negate what you can
by_age_then_name_desc = sorted(people, key=lambda p: (p[1], p[0]), reverse=True)
print(by_age_then_name_desc)

multi_key_tuple.py

people = [
    ("Bob", 25),
    ("Amy", 30),
    ("Cid", 25),
    ("Amy", 22),
]
 
# sort by age ascending, then by name ascending for ties
by_age_then_name = sorted(people, key=lambda p: (p[1], p[0]))
print(by_age_then_name)
 
# sort by age ascending, but name descending for ties -- negate what you can
by_age_then_name_desc = sorted(people, key=lambda p: (p[1], p[0]), reverse=True)
print(by_age_then_name_desc)

Stability: the guarantee that makes multi-key sorting work

A sort is stable if elements that compare equal keep their original relative order. Python’s sort has always guaranteed this — and it’s not just a nice-to-have, it’s what lets you build a multi-key sort out of several single-key sorts.

stability_demo.py

students = [
    ("Alice", "B"),
    ("Bob", "A"),
    ("Cara", "B"),
    ("Dan", "A"),
]
 
# stable sort: within each grade, the ORIGINAL relative order is preserved
by_grade = sorted(students, key=lambda s: s[1])
print(by_grade)   # Bob and Dan (grade A) stay in their original order; same for Alice/Cara

stability_demo.py

students = [
    ("Alice", "B"),
    ("Bob", "A"),
    ("Cara", "B"),
    ("Dan", "A"),
]
 
# stable sort: within each grade, the ORIGINAL relative order is preserved
by_grade = sorted(students, key=lambda s: s[1])
print(by_grade)   # Bob and Dan (grade A) stay in their original order; same for Alice/Cara

Because sorting is stable, you can sort by the least important key first, then the most important key last — each later sort only reorders groups that tied on the earlier key, leaving everything else exactly where a single tuple-key sort would have put it.

multi_pass_stable_sort.py

people = [
    ("Bob", 25),
    ("Amy", 30),
    ("Cid", 25),
    ("Amy", 22),
]
 
# two passes: sort by the secondary key first, then the primary key
step1 = sorted(people, key=lambda p: p[0])   # name (secondary), first
step2 = sorted(step1, key=lambda p: p[1])    # age (primary), last -- stable, so name order survives ties
 
# equivalent single-pass version using a tuple key
direct = sorted(people, key=lambda p: (p[1], p[0]))
 
print("two-pass:  ", step2)
print("tuple key: ", direct)
print("identical: ", step2 == direct)

multi_pass_stable_sort.py

people = [
    ("Bob", 25),
    ("Amy", 30),
    ("Cid", 25),
    ("Amy", 22),
]
 
# two passes: sort by the secondary key first, then the primary key
step1 = sorted(people, key=lambda p: p[0])   # name (secondary), first
step2 = sorted(step1, key=lambda p: p[1])    # age (primary), last -- stable, so name order survives ties
 
# equivalent single-pass version using a tuple key
direct = sorted(people, key=lambda p: (p[1], p[0]))
 
print("two-pass:  ", step2)
print("tuple key: ", direct)
print("identical: ", step2 == direct)

Custom comparators with `functools.cmp_to_keyfunctools.cmp_to_key`

key=key= needs a function that maps one element to a sortable value. Some orderings genuinely need to compare two elements directly — for those, wrap an old-style comparator with cmp_to_keycmp_to_key.

cmp_to_key_largest_number.py

from functools import cmp_to_key
 
def compare(a, b):
    # if a+b forms a bigger number than b+a, a should sort before b
    if a + b > b + a:
        return -1   # a before b
    elif a + b < b + a:
        return 1    # b before a
    return 0
 
 
nums = ["3", "30", "34", "5", "9"]
nums.sort(key=cmp_to_key(compare))
print("".join(nums))   # expect "9534330" -- the largest number formed by concatenation

cmp_to_key_largest_number.py

from functools import cmp_to_key
 
def compare(a, b):
    # if a+b forms a bigger number than b+a, a should sort before b
    if a + b > b + a:
        return -1   # a before b
    elif a + b < b + a:
        return 1    # b before a
    return 0
 
 
nums = ["3", "30", "34", "5", "9"]
nums.sort(key=cmp_to_key(compare))
print("".join(nums))   # expect "9534330" -- the largest number formed by concatenation

compare(a, b)compare(a, b) returns negative if aa belongs first, positive if bb belongs first, and 00 for a tie — the same contract as C’s qsortqsort or Java’s ComparatorComparator.

How Timsort actually works

sorted()sorted() and list.sort()list.sort() both run Timsort, a hybrid algorithm designed by Tim Peters specifically for CPython (later adopted by Java and others). The core idea: real-world data is rarely random — it usually contains long stretches that are already sorted, so Timsort looks for those stretches first instead of ignoring them.

Find runs. Scan the array for maximal runs — contiguous stretches that are already sorted ascending, or sorted descending (which get reversed in place to become ascending runs).
Extend short runs. If a natural run is shorter than a threshold (minrunminrun, usually 32-64), extend it using insertion sort — cheap and fast for small stretches.
Merge runs. Repeatedly merge pairs of runs using merge sort, using a galloping mode that speeds up merging when one run keeps “winning” many comparisons in a row (a strong signal of already-sorted structure).

diagram Timsort: find runs, then merge them mermaid

  graph TD
    A["[5, 6, 8, 2, 1, 9, 10]"] --> B["Run 1 (ascending): [5, 6, 8]"]
    A --> C["Run 2 (descending, reversed in place): [1, 2]"]
    A --> D["Run 3 (ascending): [9, 10]"]
    B --> E["Merge pairs of runs (galloping mode when one side keeps winning)"]
    C --> E
    D --> E
    E --> F["Fully sorted: [1, 2, 5, 6, 8, 9, 10]"]

timsort_best_case.py

import time
 
# nearly-sorted data: Timsort's best case, close to O(n)
nearly_sorted = list(range(200_000))
nearly_sorted[100_000], nearly_sorted[100_001] = nearly_sorted[100_001], nearly_sorted[100_000]
 
start = time.perf_counter()
nearly_sorted.sort()
elapsed_sorted = time.perf_counter() - start
 
# fully random data: Timsort's average/worst case, O(n log n)
import random
random_data = list(range(200_000))
random.shuffle(random_data)
 
start = time.perf_counter()
random_data.sort()
elapsed_random = time.perf_counter() - start
 
print(f"nearly-sorted: {elapsed_sorted * 1000:.2f} ms")
print(f"random:        {elapsed_random * 1000:.2f} ms")
print("Timsort recognizes existing order -- nearly-sorted input sorts noticeably faster.")

timsort_best_case.py

import time
 
# nearly-sorted data: Timsort's best case, close to O(n)
nearly_sorted = list(range(200_000))
nearly_sorted[100_000], nearly_sorted[100_001] = nearly_sorted[100_001], nearly_sorted[100_000]
 
start = time.perf_counter()
nearly_sorted.sort()
elapsed_sorted = time.perf_counter() - start
 
# fully random data: Timsort's average/worst case, O(n log n)
import random
random_data = list(range(200_000))
random.shuffle(random_data)
 
start = time.perf_counter()
random_data.sort()
elapsed_random = time.perf_counter() - start
 
print(f"nearly-sorted: {elapsed_sorted * 1000:.2f} ms")
print(f"random:        {elapsed_random * 1000:.2f} ms")
print("Timsort recognizes existing order -- nearly-sorted input sorts noticeably faster.")

Time and space complexity

Case	Complexity
Best (already sorted, or nearly sorted runs)	$O(n)$
Average	$O(n \log n)$
Worst	$O(n \log n)$
Space	$O(n)$ (needs a temporary merge buffer)
Stable?	Yes, always

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 2418 — Sort the People · Easy

Problem. Given namesnames and heightsheights of the same length with distinct heights, return the names sorted by decreasing height.

Constraints. 1 <= len(names) <= 10^31 <= len(names) <= 10^3, heights are distinct.

Examples. names = ["Mary","John","Emma"], heights = [180,165,170]names = ["Mary","John","Emma"], heights = [180,165,170] gives ["Mary","Emma","John"]["Mary","Emma","John"]

Editorial

zipzip keeps each height attached to its name, so a single sort reorders both consistently. Sorting the pairs is cleaner than sorting an index list and then gathering.

Time $O(n \log n)$ . Space $O(n)$ .

reverse=Truereverse=True here is safe because the heights are distinct — the comparison never falls through to the second element. If heights could repeat, reverse=Truereverse=True would also reverse the alphabetical order of tied names, which is the mixed-direction trap. The correct key in that case is key=lambda p: (-p[0], p[1])key=lambda p: (-p[0], p[1]).

["Alice","Bob","Bob"]["Alice","Bob","Bob"] with heights [155,185,150][155,185,150] shows duplicate names are harmless — it is duplicate keys that would matter.

Follow-ups: “What if heights could tie?” — use (-height, name)(-height, name); do not rely on reverse=Truereverse=True. “Sort by height ascending?” — drop reversereverse. “Avoid building pairs?” — sorted(range(n), key=lambda i: -heights[i])sorted(range(n), key=lambda i: -heights[i]) then gather, which is what you would do if the payload were expensive to copy.

LC 937 — Reorder Data in Log Files · Medium

Problem. Each log begins with an identifier, followed by either all words (letter-log) or all numbers (digit-log). Reorder so letter-logs come first, sorted by content and then by identifier; digit-logs keep their original relative order at the end.

Constraints. 1 <= len(logs) <= 1001 <= len(logs) <= 100, each log has an identifier and at least one word.

Examples. ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"] gives ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]

Editorial

This is a stability problem disguised as a sorting problem, and it is the clearest demonstration of why Python’s guaranteed-stable sort is a feature you can design around.

Time $O(n \log n \cdot L)$ — comparisons involve string content. Space $O(n)$ .

The key does three things at once:

First component 00 or 11 separates letter-logs from digit-logs.
Identical keys for all digit-logs (1,)(1,) means the sort never reorders them, so their input order survives — exactly what the problem demands, with no extra bookkeeping.
(0, rest, ident)(0, rest, ident) for letter-logs sorts by content and falls back to the identifier, which is why let1 art canlet1 art can precedes let3 art zerolet3 art zero (same first word, different content) and both precede let2 own kit diglet2 own kit dig.

split(" ", 1)split(" ", 1) with the count argument is important: splitting fully would break the content into words and lose the ability to compare it as one string.

Follow-ups: “How do you know digit-logs keep their order?” — Python’s sort is documented stable; equal keys never swap. “Without relying on stability?” — partition into two lists, sort only the letter-logs, and concatenate. “What if content ties and identifiers tie?” — impossible here, since the whole log would be identical.

LC 1329 — Sort the Matrix Diagonally · Medium

Problem. Sort each diagonal of a matrix (running from top-left to bottom-right) in ascending order, and return the matrix.

Constraints. 1 <= m, n <= 1001 <= m, n <= 100, 1 <= mat[i][j] <= 1001 <= mat[i][j] <= 100.

Examples. [[3,3,1,1],[2,2,1,2],[1,1,1,2]][[3,3,1,1],[2,2,1,2],[1,1,1,2]] gives [[1,1,1,1],[1,2,2,2],[1,2,3,3]][[1,1,1,1],[1,2,2,2],[1,2,3,3]]

Editorial

The whole insight is the invariant: moving one step down-right increases both rr and cc by one, so r - cr - c is constant along a diagonal. That turns a geometric grouping into a dictionary key.

Time $O(mn \log(\min(m, n)))$ — each diagonal has at most $\min(m, n)$ elements. Space $O(mn)$ .

Sorting each diagonal descending so that pop()pop() returns the smallest is a small but real optimisation: pop()pop() from the end is $O(1)$ , whereas pop(0)pop(0) from the front is $O(k)$ because it shifts the list.

The second write loop must traverse in the same order as the first, so that values are consumed in the order the diagonal was collected. Both loops go row by row, left to right.

[[2,1],[1,2]][[2,1],[1,2]] returning unchanged is a good check: each diagonal here has one or two already-sorted elements.

Note r - cr - c can be negative — for cells above the main diagonal — which is fine as a dict key. Using a list indexed by r - c + nr - c + n is the alternative if you prefer array indexing.

Follow-ups: “Anti-diagonals instead?” — those share r + cr + c. “Sort each diagonal descending?” — flip the sort and pop order. “Do it in place per diagonal?” — walk each diagonal, collect, sort, write back; same complexity, less memory at once.

Recap

sorted()sorted() returns a new list; list.sort()list.sort() mutates in place and returns NoneNone — never assign the result of .sort().sort() to a variable.
key=key= maps each element to a sortable value; return a tuple for multi-key ordering, negate numeric fields for a mixed ascending/descending sort.
Python’s sort is stable — equal elements keep their relative order, which is what makes multi-pass and tuple-key multi-key sorting correct.
functools.cmp_to_keyfunctools.cmp_to_key bridges old-style pairwise comparators into the key=key= interface.
Under the hood, both sorted()sorted() and .sort().sort() run Timsort: find runs, extend short ones with insertion sort, merge the rest with galloping merge sort — $O(n)$ best case, $O(n \log n)$ worst case, always stable.

Next: Binary Search Template and Variants — the bug-free template for searching a sorted sequence, plus the “search on the answer” pattern.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Python Sorting and Timsort

What you’ll learn

sorted()sorted() vs list.sort()list.sort()

Sorting with key=key=

Multi-key sorting with a tuple

Stability: the guarantee that makes multi-key sorting work

Custom comparators with functools.cmp_to_keyfunctools.cmp_to_key

How Timsort actually works

Time and space complexity

Practice — real LeetCode problems

LC 2418 — Sort the People · Easy

LC 937 — Reorder Data in Log Files · Medium

LC 1329 — Sort the Matrix Diagonally · Medium

Recap

Was this page helpful?

`sorted()sorted()` vs `list.sort()list.sort()`

Sorting with `key=key=`

Custom comparators with `functools.cmp_to_keyfunctools.cmp_to_key`