EDBT 2026 Demo / reviewers in the wild / expert
Elahe Ghasemi
dblp:322/3580
· DBLP profile ↗
3ranked-venue papers
3as first author
3since 2021 · last 2025
0009-0003-9761-6249ORCID · corroborated
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 3 · 3 first-author · 3 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2025 | Galloping in Fast-Growth Natural Merge Sorts
Elahe Ghasemi, Vincent Jugé, Ghazal Khalighinejad, Helia Yazdanyar |
Algorithmica | 1 |
| 2025 | Correction: Galloping in Fast-Growth Natural Merge Sorts
Elahe Ghasemi, Vincent Jugé, Ghazal Khalighinejad, Helia Yazdanyar |
Algorithmica | 1 |
| 2022 | Galloping in Fast-Growth Natural Merge SortsabstractWe study the impact of merging routines in merge-based sorting algorithms. More precisely, we focus on the galloping routine that TimSort uses to merge monotonic sub-arrays, hereafter called runs, and on the impact on the number of element comparisons performed if one uses this routine instead of a naïve merging routine. This routine was introduced in order to make TimSort more efficient on arrays with few distinct values. Alas, we prove that, although it makes TimSort sort array with two values in linear time, it does not prevent TimSort from requiring up to $Θ(n \log(n))$ element comparisons to sort arrays of length~$n$ with three distinct values. However, we also prove that slightly modifying TimSort's galloping routine results in requiring only $\mathcal{O}(n + n \log(σ))$ element comparisons in the worst case, when sorting arrays of length $n$ with $σ$ distinct values. We do so by focusing on the notion of dual runs, which was introduced in the 1990s, and on the associated dual run-length entropy. This notion is both related to the number of distinct values and to the number of runs in an array, which came with its own run-length entropy that was used to explain TimSort's otherwise "supernatural" efficiency. We also introduce new notions of fast- and middle-growth for natural merge sorts (i.e., algorithms based on merging runs), which are found in several merge sorting algorithms similar to TimSort. We prove that algorithms with the fast- or middle-growth property, provided that they use our variant of TimSort's galloping routine for merging runs, are as efficient as possible at sorting arrays with low run-induced or dual-run-induced complexities. Elahe Ghasemi, Vincent Jugé, Ghazal Khalighinejad |
ICALP | 1 |