Timsort Details

The Swift system sort algorithm is based on a python sorting method invented by Tim Peters in 2002, and named Timsort after the author.

The original Timsort is described here: https://svn.python.org/projects/python/trunk/Objects/listsort.txt

In the last entry, we considered the general plan behind Timsort.

The general idea is to intelligently scan the array looking for subarrays, and partitioning them away — essentially adding the subarray to a new array of those ‘partitioned’ subarrays. Once the subarrays are defined, then they are individually sorted using a method that is very quick on those subarrays: Insertion sort. Insertion sort is quick when the array is small and when the array has some predefined structure, such as always increasing or always decreasing. And those are the types of subarrays that Timsort finds when, as described above, it intelligently looks for subarrays.

After the individual subarrays are sorted, then they must be merged with each other to construct the final, sorted array.

The original ‘Tim Peters’ version of Timsort refined that last merging step further, and performed a step called ‘galloping.’ Galloping can be thought of this way: Imagine that you are merging two subarrays, A and B. Let’s say that one of them — A — happens to have a group of values that is much smaller than B. Then you compare A[0] to B[0] and you place A[0] in the final merged array. After that you compare A[1] to B[0] and again A wins and A[1] goes into the final merged array. And next you compare A[2] to B[0] and again A[2] wins and goes into the final merged array.

But now you are keeping track and you see that the A subarray has won three times in a row. And let’s say we defined three as our min number of wins before we switch to gallop mode. So now, in gallop mode, we change tactics. Our new tactic is to search through the rest of the A subarray until we find one value that loses to B[0]. And then we place all of the preceding values of the A subarray into the final merged array.

The notion here is that if the A subarray won three times in a row, it might be likely to win still more times in a row, and so let’s not keep comparing every value. Let’s instead look through A until we find a loser, and then move all the intervening values as a chunk to the final merged subarray.

This is a guess — that three wins in a row imply more wins to follow. And in many cases it might be true. But it is a guess.

It turns out that although the Python version of Timsort employs galloping, the Swift version of Timsort does not.

Swift employs simple merging without the galloping modification. https://github.com/apple/swift/pull/19717