Generalized Leapfrogging Samplesort: A Class of O(n ² n) Worst-Case Complexity and O(n n) Average-Case Complexity Sorting Algorithms
Albacea, Eliezer A.
Original · EN
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ᵏ-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 ² n) and the average-case complexity is O(n n). Keywords: Samplesort, Quicksort, Leapfrogging Samplesort, sorting, analysis of algorithms.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.