Pushing the Limits in Sequential Sorting

Stefan Edelkamp, Patrick StiegelerWAE 2000 · OpenReview

Abstract

With refinements to the WEAK-HEAPSORT algorithm we establish the general and practical relevant sequential sorting algorithm RELAXED-WEAK-HEAPSORT executing exactly n_log n_ 2_log n_ + 1 = n log n 0.9n comparisons on any given input. The number of transpositions is bounded by n plus the number of comparisons. Experiments show that RELAXED-WEAK-HEAPSORT only requires O(n) extra bits. Even if this space is not available, with QUICK-WEAK-HEAPSORT we propose an efficient QUICKSORT variant with n log n+0.2n+ o(n) comparisons on the average. Furthermore, we present data showing that WEAK-HEAPSORT, RELAXED-WEAK-HEAPSORT and QUICK-WEAK-HEAPSORT beat other performant QUICKSORT and HEAPSORT variants even for moderate values of n.
BibTeX
@inproceedings{edelkamp2000pushing,
  author = {Stefan Edelkamp and Patrick Stiegeler},
  title = {{Pushing the Limits in Sequential Sorting}},
  booktitle = {WAE},
  year = {2000},
  url = {https://openreview.net/forum?id=oyFzbocwPLP},
}

Loading related content...

Figure