Stefan Edelkamp presents 59th meeting of the PRAGUE COMPUTER SCIENCE SEMINAR

Sorting and Searching for Algorithmic Intelligence

The lecture will be followed by a discussion

ABSTRACT

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.