Timsort & Introsort: Hybrid Sorts

By Victor Arce

When you call sort() in Python, Java, or C++, you don't get bubble sort — or even plain quicksort. You get a hybrid: an algorithm that switches strategy on the fly to be fast on real data and safe in the worst case. The two you'll meet are Timsort and Introsort.

Step through how they work below.

Timsort: runs + insertion + merge

Real-world data is rarely random — it's full of stretches that are already in order. Timsort leans into that:

1. Find natural runs — scan for sequences that are already ascending (or descending). No work needed; they're free.
2. Extend short runs with insertion sort up to a minimum length. Insertion sort is the fastest thing there is on small, nearly-sorted pieces.
3. Merge the runs together, like merge sort, using clever "galloping" to skip ahead when one run dominates.

The payoff: stableStable: equal values keep their original relative order after sorting., O(n log n) worst case, and close to O(n) when the input is already partly ordered. It's the default sort in Python and Java.

Introsort: quicksort with a safety net

Introsort makes a different bet. Quicksort is wonderfully fast on average but can degrade to O(n²) on adversarial inputs. So introsort:

• runs quicksort as the main engine;
• watches the recursion depth, and if it gets too deep — the signature of a bad-pivot spiral — switches to heapsort, which guarantees O(n log n);
• drops to insertion sort for tiny subarrays, where it beats the others.

It keeps quicksort's speed while capping the worst case. It's the basis of C++'s std::sort.

Why hybrids win

Each classic sort is best at something: insertion on small/sorted data, quicksort/ merge on the average case, heapsort on worst-case guarantees. A hybrid stitches those strengths together so no single bad case can sink it. That's why a standard library never ships one textbook algorithm — it ships the combination.

Back to Sorting Algorithms