2018/09/22 by Vincent Jugé, Jugé, Vincent · 4 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genome Rearrangement Algorithms
paper · doi:10.48550/arxiv.1809.08411
openalex publication_date 2018/09/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present one stable mergesort algorithm, called \Adaptive Shivers Sort, that exploits the existence of monotonic runs for sorting efficiently partially sorted data. We also prove that, although this algorithm is simple to implement, its computational cost, in number of comparisons performed, is optimal up to a small additive linear term.