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

Abstract

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 part of size $(2^k-1)(s+1)$, where $k=O(1)$. We present a practical implementation of this class of algorithms and we show that the worst-case complexity is $O(n{\log }^{2}n)$ and the average-case complexity is $O(n\log n)$. Keywords: Samplesort, Quicksort, Leapfrogging Samplesort, sorting, analysis of algorithms.

7 pages