Timsort and Choosing a Sort in Python
26 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)In real Python code you almost never write a sort by hand. This lesson shows what the built-in does and how to choose the right tool, which is what interviewers want to hear after you can write the algorithms.
What sorted() really runs
Timsort is the hybrid sort behind sorted() and list.sort(). It finds runs that are already ordered, extends short runs with insertion sort, and merges runs. It is stable, O(n log n) at worst and O(n) on sorted input.
Python sorts with Timsort. It looks for stretches that are already in order, called runs, grows short runs with insertion sort, and joins runs with a merge like the one you wrote.
Why it is fast on real data
Real data is often partly ordered: new rows added to a sorted list, or a list that is almost in order. Timsort sees those runs and merges them, so it does far less work than a plain merge sort.
from functools import cmp_to_key
count = 0
def compare(a, b): global count count += 1 return (a > b) - (a < b)
sorted(range(1000), key=cmp_to_key(compare))print(count)Example 1 · Count the comparisons Timsort makes
from functools import cmp_to_key
count = 0
def compare(a, b): global count count += 1 return (a > b) - (a < b)
def comparisons(data): global count count = 0 sorted(data, key=cmp_to_key(compare)) return count
print(comparisons(list(range(1000))))print(comparisons(list(range(1000, 0, -1))))print(comparisons(list(range(500)) + list(range(500))))999 999 1999
What this code does
- A sorted list needs one comparison per neighbouring pair: 999.
- A reversed list is found as one descending run, which is flipped, so it costs the same. Two sorted halves cost about twice that, 1999 here, still far below random data.
Example 2 · Records with a key function
orders = [("O1", "Meera", 250), ("O2", "Arun", 90), ("O3", "Meera", 40), ("O4", "Arun", 90)]by_amount = sorted(orders, key=lambda o: o[2], reverse=True)print([o[0] for o in by_amount])['O1', 'O2', 'O4', 'O3']
What this code does
key=is called once for each item, and the sort is stable even withreverse=True.- O2 and O4 have equal amounts, so they keep their input order.
A sorted list of 1000 values needs only 999 comparisons, one per neighbouring pair. A random list needs about 8,700.
Choosing what to use in Python
Start with sorted() or list.sort(). Add key= to sort records. Use heapq for only the top few values, counting for a small range of whole numbers, and bisect.insort to keep a list sorted while adding.
import heapq
scores = [72, 95, 64, 88, 91, 55]print(sorted(scores, reverse=True)[:3])print(heapq.nlargest(3, scores))Example 3 · Top k without a full sort
import heapq
latencies = [120, 80, 95, 300, 150, 60, 210]print(heapq.nlargest(3, latencies))print(heapq.nsmallest(2, latencies))[300, 210, 150] [60, 80]
What this code does
- The heap keeps only k values, so the cost is O(n log k).
- For k close to n, sorting once with
sorted()is simpler and as fast.
Example 4 · Keep a list sorted while adding
import bisect
prices = [10, 20, 30, 40]bisect.insort(prices, 25)bisect.insort(prices, 5)print(prices)[5, 10, 20, 25, 30, 40]
What this code does
insortfinds the place in O(log n) and inserts it, which shifts items in O(n).- It suits a few additions; for many, collect the values and sort once.
Both lines print the top three. The heap version costs O(n log k), which wins when k is tiny and n is huge. For the stable multi-key sort, see the Collections lesson on sorted(), sort(), reverse and stability.
What interviewers want to hear
Name the data and the limits first: size, range, order, and whether stability or O(1) space matters. Then pick: Timsort by default, merge sort for a guaranteed bound, quick sort or quickselect for in-memory speed and k-th values, counting sort for small ranges.
Example 5 · Compare the sorts side by side
rows = [ ("Bubble", "O(n)", "O(n^2)", "O(n^2)", "O(1)", "yes"), ("Selection", "O(n^2)", "O(n^2)", "O(n^2)", "O(1)", "no"), ("Insertion", "O(n)", "O(n^2)", "O(n^2)", "O(1)", "yes"), ("Merge", "O(n log n)", "O(n log n)", "O(n log n)", "O(n)", "yes"), ("Quick", "O(n log n)", "O(n log n)", "O(n^2)", "O(log n)", "no"), ("Counting", "O(n + k)", "O(n + k)", "O(n + k)", "O(k)", "yes"), ("Timsort", "O(n)", "O(n log n)", "O(n log n)", "O(n)", "yes"),]print("sort best average worst space stable")for name, best, avg, worst, space, stable in rows: print(f"{name:<10} {best:<11} {avg:<11} {worst:<11} {space:<9} {stable}")sort best average worst space stable Bubble O(n) O(n^2) O(n^2) O(1) yes Selection O(n^2) O(n^2) O(n^2) O(1) no Insertion O(n) O(n^2) O(n^2) O(1) yes Merge O(n log n) O(n log n) O(n log n) O(n) yes Quick O(n log n) O(n log n) O(n^2) O(log n) no Counting O(n + k) O(n + k) O(n + k) O(k) yes Timsort O(n) O(n log n) O(n log n) O(n) yes
What this code does
- Read the table by the clue in the question: guaranteed bound, small range, no extra space, or stability.
- Timsort combines the best case of insertion sort with the worst case of merge sort.
Example 6 · All hand-written sorts agree with sorted()
import random
def insertion_sort(a): a = a[:] for i in range(1, len(a)): v, j = a[i], i - 1 while j >= 0 and a[j] > v: a[j + 1] = a[j] j -= 1 a[j + 1] = v return a
def merge_sort(a): if len(a) <= 1: return a left, right = merge_sort(a[:len(a) // 2]), merge_sort(a[len(a) // 2:]) out = [] while left and right: out.append(left.pop(0) if left[0] <= right[0] else right.pop(0)) return out + left + right
def quick_sort(a): if len(a) <= 1: return a p = a[len(a) // 2] return quick_sort([x for x in a if x < p]) + [x for x in a if x == p] + quick_sort([x for x in a if x > p])
random.seed(7)data = [random.randint(0, 50) for _ in range(40)]expected = sorted(data)print(insertion_sort(data) == expected, merge_sort(data) == expected, quick_sort(data) == expected)True True True
What this code does
- Testing a hand-written sort against
sorted()on random data is a quick and strong check. - Here
pop(0)is O(n), which makes this merge slower than the index version, so use indexes in a real solution.
Next step
Check your understanding
10 quick questions