4 ms·

Here you can see how an older version of quadsort beats some benchmarks that include the number of comparisons: https://www.raygard.net/2022/03/09/Re-engineerin

• SideQuark 4y ago
  I agree one can make data for which quadsort has less compares. But one can also make data where it's worse. It's provably worse over each of the 24 orderings of possible data when uniformly weighted. When your benchmarks are weighted to cases where it's better, you'll conclude it's better. But that doesn't really cover what will happen in the real world. That distribution is what will matter. As I pointed out, this line you're chasing was done decades ago. I posted one paper along this line. Things it cites and things citing it likely cover the method you're working on. Theres significant literature on your method and lots of generalizations. I'd be surprised if somehow all those researchers missed this.