Leapfrogging samplesort
Abstract
© Springer-Verlag Berlin Heidelberg 1995. In this paper, we present a practical Quicksort-based sorting algorithm that exhibits the following properties: (1) O(n(log n)2) worst case; (2) the expected number of comparisons is equal to the information-theoretic lower bound; and (3) the expected number of data interchanges is slightly higher than that of Quicksort. Considering the worst-case complexity, the average-case complexity and the simplicity of the algorithm, we claim that this algorithm is so far the most practical alternative to Quicksort. This is particularly true when one is not willing to take the risk of the worst case occuring when running Quicksort.
Source or Periodical Title
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN
3029743
Page
2021-09-01
Document Type
Article
Subject
Analysis of algorithms, Leapfrogging samplesort, Quicksort, Samplesort, Sorting
Recommended Citation
Albacea, Eliezer A., "Leapfrogging samplesort" (2021). Journal Article. 3596.
https://www.ukdr.uplb.edu.ph/journal-articles/3596