5 papers · 1 filter
On the Average Case of MergeInsertion
Florian Stober, Armin Weiß
MergeInsertion, also known as the Ford-Johnson algorithm, is a sorting algorithm which, up to today, for many input sizes achieves the best known upper bound on the number of compa…
QuickXsort - A Fast Sorting Scheme in Theory and Practice
Stefan Edelkamp, Armin Weiß, Sebastian Wild
QuickXsort is a highly efficient in-place sequential sorting scheme that mixes Hoare's Quicksort algorithm with X, where X can be chosen from a wider range of other known sorting a…
Worst-Case Efficient Sorting with QuickMergesort
Stefan Edelkamp, Armin Weiß
The two most prominent solutions for the sorting problem are Quicksort and Mergesort. While Quicksort is very fast on average, Mergesort additionally gives worst-case guarantees, b…
QuickMergesort: Practically Efficient Constant-Factor Optimal Sorting
Stefan Edelkamp, Armin Weiß
We consider the fundamental problem of internally sorting a sequence of elements. In its best theoretical setting QuickMergesort, a combination Quicksort with Mergesort with a…
BlockQuicksort: How Branch Mispredictions don't affect Quicksort
Stefan Edelkamp, Armin Weiß
Since the work of Kaligosi and Sanders (2006), it is well-known that Quicksort -- which is commonly considered as one of the fastest in-place sorting algorithms -- suffers in an es…