20 citations · 79 across the 13 of their papers we have counts for
14 papers
Multiway Powersort
William Cawley Gelling, Markus E. Nebel, Benjamin Smith +1
We present a stable mergesort variant, Multiway Powersort, that exploits existing runs and finds nearly-optimal merging orders for k-way merges with negligible overhead. This build…
Sesquickselect: One and a half pivots for cache-efficient selection
Conrado Martínez, Markus Nebel, Sebastian Wild
Because of unmatched improvements in CPU performance, memory transfers have become a bottleneck of program execution. As discovered in recent years, this also affects sorting in in…
Median-of-k Jumplists and Dangling-Min BSTs
Markus E. Nebel, Elisabeth Neumann, Sebastian Wild
We extend randomized jumplists introduced by Brönnimann et al. (STACS 2003) to choose jump-pointer targets as median of a small sample for better search costs, and present randomiz…
Applying Sorting Networks to Synthesize Optimized Sorting Libraries
Michael Codish, Luís Cruz-Filipe, Markus Nebel +1
This paper shows an application of the theory of sorting networks to facilitate the synthesis of optimized general purpose sorting libraries. Standard sorting libraries are often b…
Analysis of Pivot Sampling in Dual-Pivot Quicksort
Sebastian Wild, Markus E. Nebel, Conrado Martínez
The new dual-pivot Quicksort by Vladimir Yaroslavskiy - used in Oracle's Java runtime library since version 7 - features intriguing asymmetries. They make a basic variant of this a…
Analysis of Branch Misses in Quicksort
Conrado Martínez, Markus E. Nebel, Sebastian Wild
The analysis of algorithms mostly relies on counting classic elementary operations like additions, multiplications, comparisons, swaps etc. This approach is often sufficient to qua…