The Case for Timsort
Timsort is a sorting algorithm recently devised by its creator, Tim Peters, in 2001. It’s a popular algorithm in Python for its efficiency and speed, and so has become the de facto sorting algorithm for that language, in addition to being adopted in Java; whenever the .sort() method is called in Python, it is implementing Timsort, as is Java. Given the nature of how other sorting algorithms were created (e.g., in the “lab”, or academia), many view Timsort as the most realistic, real-world-ready sorting algorithm available since it approaches an array of items as though said array reflects real-world instances: Some data will already be sorted, some will not.
Peters is something of a guru to Pythonistas for his 20 principles of software writing, Zen of Python, which outline a typical Pythonista’s philosophy for coding. If a programmer were to call import this in the command line or anywhere Python code is executable, they’d be met with the following philosophy of Python’s coding style, Tim’s 20 principles:
Much in contrast with other programming language “philosophies,” Peters’s Zen of Python emphasizes a singular way of writing solutions to problems, whether algorithms or processes. In line with this, the Timsort sorting algorithm is based on both Insertion Sort and Merge Sort, either of which is particular to the size of the array to-be sorted; the former is great for smaller lists while the latter is more suitable for larger arrays. Most notably, Perl’s coding style is, i fact, an stark contrast to Python’s, so much so that the former’s motto is, “There’s more than one way to do it” (TMTOWTDI, or Tim Toady). We can further see this sentiment reflected in principle 14, “Although that way [the previous principle’s way] may not be obvious at first unless you’re Dutch.” Though cryptic in reference, it is generally assumed that this ambiguous, “Zen-like” principle is a reference either to Python’s progenitor, Guido van Rossum, or even (more likely) to Edsger W. Dijkstra, an early pioneer of computer systems. The latter wrote,
I thought that it was a firm principle of language design — out of concern for programming as a human activity — that in all respects equivalent programs should have few possibilities for different representations (possibility for differences ideally not going beyond the arbitrary choice of identifiers and the arbitrary ordering of syntactically unordered components). Otherwise completely different styles of programming arise unnecessarily, thereby hampering maintainability, readability and what have you.
Timsort’s time complexity is recorded at O(n log (n)), making it’s average time complexity equal to that of Quicksort and Mergesort; in best-case scenarios, whether negligible or not, Timsort will typically outperform both Quicksort and Mergesort in time complexity, though it is arguably relegated to cases where data is considered nearly sorted (e.g., real-world data) given Timsort’s stable characteristics.
The source code for Timsort is officially in C, though a simplified, Pythonic version is of use (courtesy of Nanda Javarma):
As can be seen in the code, Timsort makes use of either Insertion sort or Mergesort, contingent on the length of the array. In cases where the array is less than 64 elements, Insertion sort is incredibly fast and, in the case of Timsort, a particular type of the insertion algorithm is utilized, Binary Insertion Sort (hence, lines 1–19). In Binary Insertion Sort, the number of comparisons is reduced by employing binary search methods on the array, which locates the midway point of an array and, given whether or not the item-to-be-inserted is greater than or less than the midway point, you choose the appropriate half and halve that half and recursively repeat the process until the correct location is determined. Performance under the conditions of Binary Insertion Sort is determinately faster than normal Insertion Sort since less recursion is employed.
Timsort may not seem impressive since in many cases it could potentially implement a standardized, “lab-created” algorithm for sorting. However, given the fact that most datasets in the real world extend beyond 64 elements nowadays, Timsort’s uniqueness and power become clearer.
Timsort makes use of what are called “runs.” In a dataset, a natural run is a state of the array wherein at least two consecutive elements are currently (relative to the array’s global and local states) in either ascending or descending order. Should the two elements not be in correct ascending order, they are simply reversed in place. Timsort makes a first-pass across the array in search of such runs, while concurrently seeking to identify a minrun, or the minimum size of an ordered list within the list:
If, say, the minrun is equal to or less than 64 elements, Timsort knows to reduce itself to Binary Insertion sort, which guarantees the implementation of merging only in cases where the “weight” of a minrun is too much (e.g., cases where merging cannot be efficiently implemented because the number of minruns is greater than the power of two). In such cases where the array is greater than 64 elements, the first-pass natural-run search determines said natural runs for the sake of merging. It is ideal to delay merging until the optimized time, given the fact that an array may not be fully reduced to its set of runs without the algorithms “knowledge” of exclusive or excluded elements, not to mention the array’s size.
Though merging is a fairly standardized procedure with consummate documentation, Timsort’s unique “galloping” functionality extends its optimization beyond mere Merge sort variants. As noted, Timsort was created with real-world implications in mind: Data, especially if pulled from a .csv file, is bound to be partially ordered.
Per Peters’s own words:
Still without loss of generality, assume A is the shorter run. In galloping mode, we first look for A[0] in B. We do this via "galloping", comparing A[0] in turn to B[0], B[1], B[3], B[7], ..., B[2**j - 1], ..., until finding the k such that B[2**(k-1) - 1] < A[0] <= B[2**k - 1]. This takes at most roughly lg(B) comparisons, and, unlike a straight binary search, favors finding the right spot early in B (more on that later)...Galloping compromises by getting out fast if there isn't a long winning sub-run, yet finding such very efficiently when they exist.
In galloping mode, Timsort takes two runs (called “sub-runs” in the above quote, say X and Y) and checks, via binary search, if Y[0] could fit into X. If so, the entirety of the run is placed at the found position given the fact that the two runs are accordingly sorted due to the created of runs in Timsort’s previous step(s). Should Y[0] not fit in to Xat Y[0], then the process is reversed and Timsort attempts to insert X[0] into Y. (Also, take note of the integer 9 from image 1, above, to image 2, below.)
The above images illustrate a successful example of galloping being executed, but if there is no ultimate gallop implemented within the first few steps, galloping mode is exited. Since this process is repeated numerous times over, and since the algorithm can take note of whether galloping has been routinely successful or not, it makes it easier to deny galloping or reenter galloping, respectively.
Ultimately, data is never without some inherent, ordered structure; it is highly improbable that a natural run of more than two integers is not inherent to the dataset. Whereas Insertion sort and Merge sort appeal given their performance and their academic rigor, Timsort is more pragmatic.
