Skip to content
Tutorials Center
My learning

Topics

Lesson 85 of 225 ยท Sorting

Shell Sort, Timsort and Hybrid Sorts

Learn Shell sort gap sequences, how Python's Timsort uses runs and merging, and how introsort mixes quick, heap and insertion sort. Includes comparison counts.

The sorts in the earlier lessons are the pure, textbook versions. Production libraries rarely use a pure version. They glue together several algorithms, each used where it is strongest: insertion sort for tiny pieces, merge sort for stability, quick sort for speed, heap sort as a safety net. This lesson covers the ideas behind the most important hybrids, and one clever relative of insertion sort, Shell sort, that deserves a place of its own.

You will implement Shell sort and compare gap sequences, take a guided tour of Timsort (the algorithm behind Python's sorted() and list.sort()) with a runnable miniature version, build introsort (used by C++ std::sort implementations), and finish with a practical answer to the question "which sort should I use?".

Shell sort: insertion sort with long jumps

Insertion sort is fast when the list is nearly sorted, but slow when an element is far from its final place, because each swap moves it only one position. Donald Shell's idea (1959): first sort elements that are far apart, then closer, and finally do an ordinary insertion sort when the list is almost sorted already.

Concretely, choose a decreasing sequence of gaps, ending with 1. For each gap g, run an insertion sort over all elements g apart: positions 0, g, 2g, ...; then 1, 1+g, ...; and so on. We say the list is g-sorted afterwards. The final pass with gap 1 is plain insertion sort, but it has little work left.

TEXT
list: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]      gap = 5

pairs compared and fixed: (9,4) (8,3) (7,2) (6,1) (5,0)
-> [4, 3, 2, 1, 0, 9, 8, 7, 6, 5]         far-away elements travelled 5 steps in one swap

gap = 2, then gap = 1 finish the job on an almost sorted list
Python Shell sort with a trace

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The gap sequence is the whole story

The running time depends entirely on the gaps. Shell's original sequence n/2, n/4, ..., 1 is easy to write but can be O(nยฒ) in the worst case, because the early gaps are all even and some elements never meet until the last pass. Better sequences mix odd numbers:

Sequence Gaps Known worst case
Shell (1959) n/2, n/4, ..., 1 O(nยฒ)
Knuth (1973) 1, 4, 13, 40, ... (3g + 1) O(n^1.5)
Ciura (2001) 1, 4, 10, 23, 57, 132, 301, 701, ... not proven; best known in practice
Python Comparing gap sequences by counting comparisons

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Plain insertion sort needs about nยฒ/4 comparisons on shuffled data (around a million for n = 2,000), while any Shell variant needs only a small fraction of that. Shell sort is in place (O(1) extra space), not stable, simple to code, and a good choice for embedded systems where code size matters. It is still beaten by O(n log n) sorts for large inputs.

Timsort: Python's sort

Since Python 2.3, list.sort() and sorted() use Timsort, designed by Tim Peters. It is built on one observation: real data is rarely random. Logs arrive in time order, a spreadsheet column is mostly sorted, a list is two sorted lists glued together. Timsort finds this existing order and exploits it.

The algorithm in four ideas:

  1. Find natural runs. Scan the list for stretches that are already ascending (or strictly descending, which it reverses in place). Each such stretch is a run.
  2. Extend short runs. Very short runs are not worth merging. Timsort picks a minrun (between 32 and 64) and extends any shorter run to that length with binary insertion sort, which is quick for small pieces.
  3. Merge runs. Runs are pushed on a stack and merged pairwise in an order that keeps the merges balanced (rules on the lengths of the top runs on the stack guarantee O(n log n) overall). The merge is stable.
  4. Galloping. While merging, if one run keeps "winning" many comparisons in a row, Timsort switches to an exponential search to skip ahead in bulk, which makes merging a block of elements that are all smaller (or larger) than the other side almost free.
TEXT
input:     5 4 3 2 1 | 6 7 8 9 20 | 10 11
runs:      [5 4 3 2 1] -> reversed to [1 2 3 4 5]   [6 7 8 9 20]   [10 11]
merge:     [1 2 3 4 5] + [6 7 8 9 20]            -> [1 2 3 4 5 6 7 8 9 20]
merge:     [1 2 3 4 5 6 7 8 9 20] + [10 11]      -> sorted

Let us build a miniature of this. It finds runs, extends short ones with insertion sort to minrun, and merges neighbors. (The real Timsort uses a careful merge-order stack and galloping; we skip those details to keep the code readable.)

Python A miniature Timsort

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You can see the three kinds of work: a strictly descending run that is reversed, an ascending run, and a short leftover piece. A run shorter than minrun is extended with insertion sort when more elements follow it; here the list simply ends. Try minrun=8 to see the first run absorb extra elements. For lists shorter than 64 elements, minrun equals n, so Timsort is simply binary insertion sort, which is exactly right for small lists.

What the real Timsort achieves

Here is what makes sorted() special. We can count comparisons because Python's sort only ever uses < between elements. The wrapper class below counts each call.

Python Counting the comparisons Python's sort makes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Sorted, reversed and all-equal inputs need only n - 1 comparisons: Timsort discovers a single run, checks it, and is done. That is O(n) for these cases, while the shuffled case is about n log n. Nearly sorted data costs little more than the number of out-of-place items require. These adaptive properties come on top of the guarantees: worst case O(n log n), stable, and O(n) extra space (it merges with a temporary buffer holding the smaller run).

Because Timsort is stable, you can sort in multiple passes: sort by the secondary key first, then by the primary key, and the secondary order survives within equal primary keys. See Sorting Basics.

Introsort: quick sort with a safety net

Quick sort is the fastest general-purpose sort in practice, but it has the O(nยฒ) worst case. Introsort (introspective sort, David Musser, 1997) removes the worst case with a simple rule: run quick sort, but count the recursion depth. If the depth passes about 2ยทlogโ‚‚ n, the pivots are clearly performing badly, so switch to heap sort for that part. For tiny pieces (under about 16 elements) switch to insertion sort, which has the lowest overhead on little arrays.

The result: quick sort's typical speed, heap sort's O(n log n) guarantee, and good behavior on small ranges. This is the design of the std::sort implementation in common C++ standard libraries. Here it is in Python, with a counter showing which strategy was used:

Python Introsort: quick sort, heap sort and insertion sort together

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With the normal limit of about 2ยทlogโ‚‚ n, the counters show quick sort partitions plus many small insertion sorts, and no heap sort at all: on ordinary data the safety net is never needed. When we artificially lower the depth limit to 2, the unfinished ranges are handed to heap sort and the result is still correct. That is the safety net at work.

Other hybrids you will meet

  • Pattern-defeating quicksort (pdqsort), used by Go and Rust's unstable sorts, extends introsort with detection of already sorted and many-duplicates inputs.
  • Merge sort with insertion sort cutoff: used in Java for objects (a Timsort variant) because stability matters for objects.
  • Dual-pivot quicksort: Java's Arrays.sort for primitive types, with two pivots and three partitions.

You do not need to memorize these. The pattern is always the same: use a fast general algorithm, fall back to a guaranteed one when it struggles, and use something simple for small ranges.

Which sort should I use?

Situation Choice
Ordinary Python code sorted() / list.sort(): Timsort, stable, adaptive
Need stability and guaranteed O(n log n) Merge sort or Timsort
Tiny or nearly sorted list in hand-written code Insertion sort
Memory is very tight, worst case matters Heap sort
Small integer keys Counting or radix sort
Only need the top k or k-th item Quickselect or heapq.nsmallest
Teaching, interviews Know all of them and their trade-offs

Common mistakes

  • Writing your own sort in production Python. sorted is written in C and adaptive; a pure Python merge or quick sort will be far slower.
  • Using the Shell sort gap sequence n/2, n/4, ... and expecting O(n log n). Use Knuth or Ciura gaps.
  • Assuming sorted is O(n log n) for every input. It is at most O(n log n); on data with existing order it can be as little as O(n).
  • Confusing stability guarantees. Timsort is stable; introsort, heap sort and Shell sort are not.
  • Forgetting that Python's sort needs only <. Custom classes need __lt__ (or a key=) to be sortable.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a gap of g mean in Shell sort?

    Each pass insertion-sorts the elements at positions i, i+g, i+2g, ... so that far-apart elements move quickly towards their final places.
  2. 2. Which of these is a natural run that Timsort detects?

    Timsort scans for stretches that are already sorted (reversing strictly descending ones) and merges them instead of sorting from scratch.
  3. 3. How many comparisons does Python's sort need for a list that is already sorted?

    It finds one long run by comparing each element to its neighbor, which takes n - 1 comparisons, and then there is nothing to merge.
  4. 4. Why does introsort switch to heap sort at a certain recursion depth?

    A deep recursion means the partitions are unbalanced. Heap sort has no bad case, so switching to it caps the worst case at O(n log n).
  5. 5. Which statement about Timsort is true?

    Timsort is a stable merge-based hybrid with O(n log n) worst-case time and up to O(n) temporary space.

Summary

  • Shell sort runs insertion sort with decreasing gaps; the gap sequence decides the speed (Knuth and Ciura beat n/2, n/4, ...). It is in place and not stable.
  • Timsort (Python's sorted and list.sort) finds natural runs, extends short ones with binary insertion sort, merges them stably and gallops through lopsided merges.
  • Timsort is O(n log n) in the worst case, O(n) on already ordered input, stable, and uses up to O(n) extra space.
  • Introsort is quick sort plus a heap sort fallback at a depth limit plus insertion sort for small ranges, giving fast typical speed and an O(n log n) worst case.
  • In real Python code, use sorted; know the others for interviews and for understanding trade-offs.

Next: Sorting Problems and Applications, where sorting becomes the first step of solving other problems.