4 ms·

Well, blitsort's performance is exceptional in the sense that it's 15% faster than the next fastest stable in-place sort. As for stability, it's useful when yo

Well, blitsort's performance is exceptional in the sense that it's 15% faster than the next fastest stable in-place sort. As for stability, it's useful when you need to sort a table with an integer index. So it might be of value to database software. I probably should point out some of the weakness on the README. Agreed on pdqsort being 3x slower worst case on "killer" input, but it's my understanding that's why it's not being used to replace std::sort. As for runs of 50, haven't benched those, though I assume gridsort (https://github.com/scandum/gridsort https://github.com/scandum/gridsort) would handle those rather well.

mlochbaum 5y ago
I guess that makes sense, but I never would have guessed that the category is in-place stable algorithms as it's only mentioned in the "about" line and not the text itself. Sorting on an integer key isn't the same as sorting a list of integers. They have different performance considerations.
- scandum 5y ago
  I updated the README slightly, it's mentioned twice now. :) As for performance considerations, blitsort's performance on integers is indicative of its performance on strings, while this isn't the case for pdqsort. I haven't ran a specific benchmark, but I assume that on string data blitsort will beat pdqsort for every metric except random with many equal items.
nightcracker 5y ago
> Agreed on pdqsort being 3x slower worst case on "killer" input, but it's my understanding that's why it's not being used to replace std::sort. This is just not true. Introsort (the current std::sort in all C++ compilers I know of) also has 'killer' inputs, and will switch to heapsort twice as slow than than pdqsort does in those. Worse, the libc++ implementation of std::sort has a quadratic killer sequence that I found 7 years ago, and it is still not fixed: https://bugs.llvm.org/show_bug.cgi?id=20837 https://bugs.llvm.org/show_bug.cgi?id=20837. In my opinion there is no good reason that pdqsort is not adopted yet as std::sort as it is faster for many patterns, faster for random input and rarely if ever slower. In fact, pdqsort is the standard unstable sorting algorithm in Rust: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort_unstable https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor... Note that any deterministic quicksort variant that does not spend a lot of time on choosing its pivots will always have some 'killer' pattern that forces it to use its fallback algorithm (or worse, go O(n^2)), as you can always shuffle the input array such that poor pivots are chosen. What pdqsort does is shuffle things around so that those 'killer' patterns are a lot less trivial, and are not as likely to occur in real-world input. For me determinism was very important so I didn't do it in https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort, but note that the variant implemented in Rust uses non-deterministic swapping and thus it is impossible to force a 'killer' input against it.
- scandum 5y ago
  Given how fast pdq is there's indeed no reason not to adopt it. Probably the usual 'not invented here' mindset.

mlochbaum 5y ago

I guess that makes sense, but I never would have guessed that the category is in-place stable algorithms as it's only mentioned in the "about" line and not the text itself. Sorting on an integer key isn't the same as sorting a list of integers. They have different performance considerations.

scandum 5y ago
I updated the README slightly, it's mentioned twice now. :) As for performance considerations, blitsort's performance on integers is indicative of its performance on strings, while this isn't the case for pdqsort. I haven't ran a specific benchmark, but I assume that on string data blitsort will beat pdqsort for every metric except random with many equal items.

nightcracker 5y ago

> Agreed on pdqsort being 3x slower worst case on "killer" input, but it's my understanding that's why it's not being used to replace std::sort. This is just not true. Introsort (the current std::sort in all C++ compilers I know of) also has 'killer' inputs, and will switch to heapsort twice as slow than than pdqsort does in those. Worse, the libc++ implementation of std::sort has a quadratic killer sequence that I found 7 years ago, and it is still not fixed: https://bugs.llvm.org/show_bug.cgi?id=20837 https://bugs.llvm.org/show_bug.cgi?id=20837. In my opinion there is no good reason that pdqsort is not adopted yet as std::sort as it is faster for many patterns, faster for random input and rarely if ever slower. In fact, pdqsort is the standard unstable sorting algorithm in Rust: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort_unstable https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor... Note that any deterministic quicksort variant that does not spend a lot of time on choosing its pivots will always have some 'killer' pattern that forces it to use its fallback algorithm (or worse, go O(n^2)), as you can always shuffle the input array such that poor pivots are chosen. What pdqsort does is shuffle things around so that those 'killer' patterns are a lot less trivial, and are not as likely to occur in real-world input. For me determinism was very important so I didn't do it in https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort, but note that the variant implemented in Rust uses non-deterministic swapping and thus it is impossible to force a 'killer' input against it.

scandum 5y ago
Given how fast pdq is there's indeed no reason not to adopt it. Probably the usual 'not invented here' mindset.