4 ms·

Adding an option to shoot yourself in the foot is bad API design and a premature optimization. For the most part, it is rare to have both fully randomized data

Adding an option to shoot yourself in the foot is bad API design and a premature optimization. For the most part, it is rare to have both fully randomized data and a need to sort it. One way to test the quality of a psuedo random number generator is to count ascending and descending runs https://en.wikipedia.org/wiki/Diehard_tests https://en.wikipedia.org/wiki/Diehard_tests. This suggests that runs are hard to get rid of even when your trying to do it on-purpose. The Timsort algorithm expends a little effort to see if runs are present (which is common) so that it can dramatically reduce the effort required to sort. Taking the check out is likely to be a bad idea in general -- "Hey, I'll speed things up by a few percent by removing the check for a high-speed shortcut. Now, give me a raise." In a way, this micro-optimization isn't much more interesting than adding a flag to indicate that the data is already sorted. "Hey, I sped-up the sort routine by 100% because I already happened to know that the data was already sorted. Another raise please." Lastly, I question the benchmarking procedure. One uses numpy arrays without any object overhead and the other timing uses plain python lists. This is an apples-to-oranges comparison that doesn't allow you to draw any meaningful conclusions about the relative speed of the two algorithms. Very few people have crossed light sabers with Tim Peters and won. I'm amazed at how many people think that the first ideas that pop into their head will be better than decades of experience, deep analysis, and careful design. This is mature code, widely studied, and adopted in multiple languages.

scythe 12y ago
The difference between merge sort and tim sort is not "removing a check"; timsort is actually a different algorithm. In the ordinary sense of the word, there is no check. In fact, the use of insertion sort is most important to speed up sorting random data, because the real advantage of insertion sort is that for small enough chunks -- anything that fits in a few cache lines -- the amount you save on comparisons vastly exceeds the amount you spend on swapping. Most well-written sort functions use insertion sort at small enough sizes. The adaptive speedup in timsort does not come from adopting ideas in insertion sort; rather, it comes from strand sort. http:// http:// en.wikipedia.org/wiki/Strand_sort As to the speedup, who knows? As you've stated, this is an apples-to-oranges comparison. It depends on the Python vs NumPy object model, and it's pretty suspicious to see mergesort beating quicksort.

scythe 12y ago

The difference between merge sort and tim sort is not "removing a check"; timsort is actually a different algorithm. In the ordinary sense of the word, there is no check. In fact, the use of insertion sort is most important to speed up sorting random data, because the real advantage of insertion sort is that for small enough chunks -- anything that fits in a few cache lines -- the amount you save on comparisons vastly exceeds the amount you spend on swapping. Most well-written sort functions use insertion sort at small enough sizes. The adaptive speedup in timsort does not come from adopting ideas in insertion sort; rather, it comes from strand sort. http:// http:// en.wikipedia.org/wiki/Strand_sort As to the speedup, who knows? As you've stated, this is an apples-to-oranges comparison. It depends on the Python vs NumPy object model, and it's pretty suspicious to see mergesort beating quicksort.