4 ms·

I was hoping to see some benchmark numbers

• varenc 4y ago
  Creating a single benchmark seems tricky since Timsort’s key strength is it performs particularly well on real world data where subsequences of the input are often already sorted (runs). With random data it should have O(n log n) time like any other comparison sort. So with benchmarking the challenge is coming up with a set of real world-like test data that feels representative but isn’t just excessively playing to Timsort’s strengths. Not everyone’s “real world” data is the same.
  • sshine 4y ago
    This kind of almost sorted data is easily synthesised with any degree of already-sorted-ness.
    • varenc 4y ago
      Certainly! But then how do you decide what degree of already-sorted-ness fairly represents real world data?
      • not2b 4y ago
        By collecting a lot of real world data?
      • sshine 4y ago
        You don’t have to agree on any one degree. You can set up a giant matrix with lengths on one axis, and the sortedness on the other. Each cell can have a color indicating if TimSort beats, say, some other hybrid of MergeSort; green shades suggest TimSort is winning, red shades suggest the contender is winning. For each cell, do multiple runs with those sortedness/length parameters and pick the average.
  • hinkley 4y ago
    I'm trying to recall what the expected level of clustering is even for properly random inputs. A few years before Timsort there was someone randomly shuffling the input in order to avoid the reverse-order corner case that kills so many sort algorithms. For truly random inputs, about half of the entries should be pairs that are partially ordered, and 25% runs of 3, no? And if memory serves Timsort also has a fast path for strictly decrementing runs as well, where it amortizes some of the comparisons done in the scan phase to do a blind reverse() call.
• lifthrasiir 4y ago
  CPython source code contains a separate documentation [1] for a detailed description and discussion for the algorithm. TimSort optimizes for the number of comparisons (which are expensive in Python since each comparison can call a Python function) so all numbers are given as such. [1] https://github.com/python/cpython/blob/main/Objects/listsort.txt https://github.com/python/cpython/blob/main/Objects/listsort...
  • hinkley 4y ago
    Number of comparisons is a particular sore point for me. Nobody is sorting integers. This is the goddamned 21st century, not 1980's era video games. Just stop. Show me a sort algorithm that is still efficient with five pointer indirections in compare() and I'm satisfied. Show me primitive data types and I start to wonder what you're hiding (read: lying about).
    • elcomet 4y ago
      What are you talking about? I sort integers every day
    • mort96 4y ago
      Sorting integers, floats and strings are surely some of the most widely used ways of sorting? You have some table-like thing, you want to sort it by some numeric column or alphabetically by some string column. Sorting some generic structure is surely the edge case, and even when you do that, surely the most common case is to compare one or two structure fields which are either ints, floats or strings. In languages which try to be efficient, surely an expensive compare function is the outlier.