Sorting and Searching for Algorithmic Intelligence

QuickXsort is a highly efficient in-place sequential sorting scheme that mixes Hoare’s Quicksort algorithm with X, where X can be chosen from a wider range of other known sorting algorithms, like Heapsort, Insertionsort and Mergesort. Its major advantage is that QuickXsort can be in-place even if X is not. By doing so the mean number of comparisons can be reduced down to n*log(n) – 1.4112*n + o(n) for a remaining gap of only 0.0315*n comparisons to the lower bound.

On the practical side, BlockQuicksort beats standard library implementations and has been included in libcxx. I will also introduce a variant of a binary heap that operates in-place, executes minimum and insert in worst-case constant time, and extract-min in O(log(n)) worst-case time, while involving at most log(n) + O(1) element comparisons. These efficiencies surpass lower bounds known for standard binary heaps, thereby resolving a long-standing theoretical debate.