Tim Sort

TimSort is an adaptive, stable, in-place sorting algorithm developed by TimPeters.

It takes advantage of existing structure in a list, allowing it to perform n-1 comparisons on a list which is already in order or in strictly-descending (reverse) order. To do this, TimSort walks the list, finding "runs" of elements already in ascending order or in strictly descending order, a "run." If the run is in strictly descending order, TimSort reverses it in place (hence why the run must be strictly descending, as this operation would otherwise not maintain TimSort's stability). Then, if the run is less than a chosen "minrun" size, TimSort uses InsertionSort to bulk it up to minrun elements. The value of minrun is calculated such that, where n is the size of an array, n/minrun is a power of two or slightly less than a power of two, thus ensuring balanced merges on random data.

In order to take advantage of cached runs, TimSort always tries to merge runs as soon as it is optimal to do so. However, TimSort also attempts to keep the merges balanced. To do this, it records each run created on a stack. It then analyzes the top three runs of the stack, and attempts to maintain the following size invariants:

Last run < Second to last run Last run + Second to last run < Third to last run

After each run is computed, something equivalent the following pseudocode is executed:

   While (true):
      let A = pop(stack);
      let B = pop(stack);
      let C = pop(stack);
      If A + B > C:
         push(stack, merge(B, C));
         push(A);
      Else If A > B:
         push(stack, C);
         push(stack, merge(A, B);
      Else:
       break;

This makes it more likely that runs will be merged while they are still in cache, while still allowing balanced merges.

The merge algorithm itself is an adaptation in TimSort. In order to use less space, merges are done partially in-place, with the smaller of two adjacent runs being copied into scratch space. Because the smaller run is always chosen, TimSort will never need more than O(N/2) extra space. Then, the "insertion point" is found with a binary search. Merging then proceeds as normal, unless one list is consistently greater than the other a certain (but not fixed!) number of times, known as min_gallop. If this happens, "galloping mode" is entered, in which the merges use an exponential-binary search to find how many of one list to copy before the other will win again. (Exponential search is used because it takes no more than twice as much time as standard binary search in the worst case, and because it wins as long as the sub-run of winning elements is not very long.) Every time galloping is successful in saving time, min_gallop is decremented. Every time galloping is unsuccessful in saving time, min_gallop is incremented. If a list has similar amounts of structure in its beginning and end, TimSort's merges should become better and better as the algorithm progresses.

All of these enhancements produce a sort which, in addition to its theoretical O(n log n) worst case and O(n) best case, also has "supernatural" performance on real world data (without needing a large amount of special cases, as Python's previous sorting algorithm, a tuned IntroSort?, eventually came to have), and good locality of reference.

Original page:

TimSort is an adaptive, stable, in-place sorting algorithm developed by TimPeters.

It performs "supernaturally fast" on partially-ordered lists, doing only N-1 comparisons on a list which is already sorted or sorted in the reverse order.

Essentially, TimSort works by walking the list and finding "runs" which are already sorted in forward or reverse order. It then reverses any backward runs in-place. Any runs below a chosen minimum run size are bulked up to that size using InsertionSort, which somehow speeds up average time, though I can't see how. According to wikipedia, the optimum minrun size for 64 elements is 32. Finally, TimSort merges the lists.

TimSort, at least as far as this AnonymousDonor has seen it, is not an easily-understood algorithm; the average TimSort source code listing is full of MagicNumbers? relating to minrun size and complicated branching statements.

For my take on the BareMinimum? of TimSort, see TimSortSimplified.

OK, I've looked at it. The InsertionSort is actually an optimisation of Merge when one of the runs is small; let's call it insertion-merge. Insertion-merge takes O(m log2 n) comparisons and O(mk) moves, where m is the number of elements in the list being inserted, n is the number of elements in the list being inserted into, and k is the average distance between the element to be inserted and its final position.

For small m, O(m log2 n) will usually be smaller than the O(n) worst-case of normal merge, and also takes less memory. For large m, such that m >= n, you get O(n log n) comparisons, much worse than the normal-case O(n). In this case, normal merge will be better suited for merging the runs.