🧮Timsort
Also known as Tim Sort, TimSort
The sort Python uses. It finds runs already in order and merges them.
Think of it like
Think of it like a deck that is partly in order. Keep the neat runs, then join them.
Example
Jack sorts 100,000 prices that were in order until 50 new ones joined the end. Timsort finds the one long run, sorts the 50 and merges them, far faster than a full sort.
Why it matters
Real data is often partly sorted already. Timsort is built to spot that and skip the work, which is why sorted is so fast in practice.
Definition
Example code
python
>>> people = [("Emma", 9), ("Tom", 7), ("Jack", 9)]
>>> sorted(people, key=lambda p: p[1])
[('Tom', 7), ('Emma', 9), ('Jack', 9)]Common mistake
Key takeaways
- 1Finds runs. Runs already in order are kept.
- 2Merges them. Stable, and never worse than n log n.
- 3Adaptive. Fast on nearly sorted data.