2 papers
math.CO2021
On Arithmetically Progressed Suffix Arrays and related Burrows-Wheeler Transforms
Jacqueline W. Daykin, Dominik Köppl, David Kübel +1
We characterize those strings whose suffix arrays are based on arithmetic progressions, in particular, arithmetically progressed permutations where all pairs of successive entries…
cs.DS2019
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…