Reducing the number of comparisons
Closed this issue · 2 comments
Finally getting around to replacing those linear searches with something more intelligent, to drastically lower the number of comparisons needed when there aren't very many unique values within the array. Right now even after a few comparison optimizations it's still using 30% more compares than __inplace_stable_sort() in one test case. Should be able to do a lot better!
The development branch has these changes added, and now uses fewer comparisons __inplace_stable_sort(), although it's about 10% slower than the previous version of WikiSort due to the added computational complexity.
Hm, it's also about 15-20% faster in situations where comparisons aren't lightning-fast, due to the significant reduction in comparisons. So while it looks pretty poor in the current benchmarks, it looks like it might be better in real-world use. Maybe I should come up with better benchmarks to draw attention to this.