20 citations · 97 across the 21 of their papers we have counts for
Showing 2016Show all
2 papers · 1 filter
cs.DS2016
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…
cs.DS2016★ 5 cited
Quicksort Is Optimal For Many Equal Keys
Sebastian Wild
I prove that the average number of comparisons for median-of- Quicksort (with fat-pivot a.k.a. three-way partitioning) is asymptotically only a constant times worse than t…