Zobrazeno 1 - 10
of 217
pro vyhledávání: '"Nebel, Markus"'
Publikováno v:
ALENEX 2023
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 builds on Powersort (Munro & Wild, ESA2018), which has recently replaced Ti
Externí odkaz:
http://arxiv.org/abs/2209.06909
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 internal memory. Since partitioning around several pivots reduces overal
Externí odkaz:
http://arxiv.org/abs/1810.12322
We extend randomized jumplists introduced by Br\"onnimann et al. (STACS 2003) to choose jump-pointer targets as median of a small sample for better search costs, and present randomized algorithms with expected $O(\log n)$ time complexity that maintai
Externí odkaz:
http://arxiv.org/abs/1609.08513
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 based on combinations of the classic Quicksort algorithm with insertion
Externí odkaz:
http://arxiv.org/abs/1505.01962
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 algorithm use less comparisons than classic single-pivot Quicksort. In
Externí odkaz:
http://arxiv.org/abs/1412.0193
The analysis of algorithms mostly relies on counting classic elementary operations like additions, multiplications, comparisons, swaps etc. This approach is often sufficient to quantify an algorithm's efficiency. In some cases, however, features of m
Externí odkaz:
http://arxiv.org/abs/1411.2059
Autor:
Nebel, Markus E., Wild, Sebastian
The new dual-pivot Quicksort by Vladimir Yaroslavskiy - used in Oracle's Java runtime library since version 7 - features intriguing asymmetries in its behavior. They were shown to cause a basic variant of this algorithm to use less comparisons than c
Externí odkaz:
http://arxiv.org/abs/1403.6602
Autor:
Wild, Sebastian, Nebel, Markus E.
Publikováno v:
In L. Epstein & P. Ferragina (Eds.), ESA 2012 (LNCS 7501, pp. 825-836). Springer Berlin/Heidelberg
Recently, a new Quicksort variant due to Yaroslavskiy was chosen as standard sorting method for Oracle's Java 7 runtime library. The decision for the change was based on empirical studies showing that on average, the new algorithm is faster than the
Externí odkaz:
http://arxiv.org/abs/1310.7409
Autor:
Jin, Emma Yu, Nebel, Markus E.
In this paper we prove a $q$-analogue of Koshy's formula in terms of the Narayana polynomial due to Lassalle and a $q$-analogue of Koshy's formula in terms of $q$-hypergeometric series due to Andrews by applying the inclusion-exclusion principle on D
Externí odkaz:
http://arxiv.org/abs/1309.0949
There is excitement within the algorithms community about a new partitioning method introduced by Yaroslavskiy. This algorithm renders Quicksort slightly faster than the case when it runs under classic partitioning methods. We show that this improved
Externí odkaz:
http://arxiv.org/abs/1306.3819