Generalized Leapfrogging Samplesort: A Class of $O(n{\log }^{2}n)$ Worst-Case Complexity and $O(n\log n)$ Average-Case Complexity Sorting Algorithms

Eliezer A. Albacea

The original Leapfrogging Samplesort operates on a sorted sample of size $s$ and an unsorted part of size $s+1$. We generalize this to a sorted sample of size $s$ and an unsorted p…