2015/08/02 by John Ellis, Ellis, John, Ulrike Stege +1
Computer Science · Decision Sciences · Mathematics · #Advanced Combinatorial Mathematics #Advanced Database Systems and Queries #Algorithms and Data Compression #Data Quality and Management #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1508.00292
openalex publication_date 2015/08/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We reconsider a recently published algorithm (Dalkilic et al.) for merging\nlists by way of the perfect shuffle. The original publication gave only\nexperimental results which, although consistent with linear execution time on\nthe samples tested, provided no analysis. Here we prove that the time\ncomplexity, in the average case, is indeed linear, although there is an\nOmega(n2) worst case. This is then the first provably linear time merge\nalgorithm based on the use of the perfect shuffle. We provide a proof of\ncorrectness, extend the algorithm to the general case where the lists are of\nunequal length and show how it can be made stable, all aspects not included in\nthe original presentation and we give a much more concise definition of the\nalgorithm.\n