Sorting Comparison

You've now coded five sorting algorithms by hand: Bubble, Selection, Insertion, Merge, and Quick sort. Interviewers rarely ask you to write a sixth from scratch — what they actually want is for you to pick the right one and justify the pick with time complexity, space complexity, stability, and whether it sorts in-place. This lesson puts all five side by side in one table, then looks at what Python's own sorted() and list.sort() do under the hood — a single, carefully engineered algorithm called Timsort — and how the key= parameter lets you sort by anything without writing a custom comparison function.

The Full Comparison Table

Python's Built-In sorted() and list.sort() — Timsort

Every Python list already knows how to sort itself, and you should reach for the built-in before ever hand-rolling a sort in real code. Both entry points run the same algorithm, Timsort (named after Tim Peters, who wrote it for CPython in 2002 — it's since been adopted by Java for object arrays, and by Android and V8 as well):

• sorted(iterable) — works on any iterable (list, tuple, string, dict keys, generator...) and always returns a brand-new list, leaving the original untouched.
• some_list.sort() — a method that exists only on list, sorts it in-place, and returns None (a common beginner bug: writing my_list = my_list.sort() silently sets my_list to None).

numbers = [5, 2, 9, 1, 5, 6]

# sorted() -- returns a new list, original is untouched
result = sorted(numbers)
print(result)   # [1, 2, 5, 5, 6, 9]
print(numbers)  # [5, 2, 9, 1, 5, 6] -- unchanged

# list.sort() -- sorts in-place, returns None
numbers.sort()
print(numbers)  # [1, 2, 5, 5, 6, 9] -- the original list is now sorted

# Both accept reverse=True for descending order
print(sorted(numbers, reverse=True))  # [9, 6, 5, 5, 2, 1]

Time complexity: O(n log n) worst case, O(n) best case on already-sorted or nearly-sorted input (Timsort detects existing order and exploits it — this is what "adaptive" means below). Space complexity: O(n) for the temporary merge buffer Timsort allocates.

Timsort's Three Defining Properties

The key= Parameter — Sorting By Anything

Rather than writing a custom two-argument comparison function (Python 3 removed the old cmp= parameter entirely), both sorted() and list.sort() take a key= function: it's called once per element, and the results are what actually get compared — the original elements are then arranged to match that comparison order.

# Sort strings by length instead of alphabetically
words = ["banana", "kiwi", "fig", "apple"]
print(sorted(words, key=len))
# ['fig', 'kiwi', 'apple', 'banana'] -- 3, 4, 5, 6 letters

# Sort a list of tuples by their second element
scores = [("Alice", 72), ("Bob", 95), ("Cara", 88)]
print(sorted(scores, key=lambda pair: pair[1], reverse=True))
# [('Bob', 95), ('Cara', 88), ('Alice', 72)] -- highest score first

# Sort case-insensitively without changing the original casing
names = ["bob", "Alice", "cara"]
print(sorted(names, key=str.lower))
# ['Alice', 'bob', 'cara']

# Sort dicts/objects with operator.itemgetter / attrgetter (faster than a lambda)
from operator import itemgetter

people = [{"name": "Alice", "age": 30}, {"name": "Bob", "age": 25}]
print(sorted(people, key=itemgetter("age")))
# [{'name': 'Bob', 'age': 25}, {'name': 'Alice', 'age': 30}]

Time complexity: O(n log n) — the key function itself runs in O(1) per call in all four examples above (each is called exactly once per element, not once per comparison, which is why key= is efficient even for an expensive-to-compute key). Space complexity: O(n) — one cached key value per element, plus Timsort's own O(n) merge buffer.

A Decision Checklist For Interviews