2009/07/04 by Travis Gagie, Yakov Nekrich, Gagie, Travis +1
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Optimization and Search Problems #cs.DS
paper · pdf · doi:10.48550/arxiv.0907.0741
arxiv created 2009/07/04 · openalex publication_date 2009/07/04 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Although many authors have considered how many ternary comparisons it takes to sort a multiset S of size n, the best known upper and lower bounds still differ by a term linear in n. In this paper we restrict our attention to online stable sorting and prove upper and lower bounds that are within (o (n)) not only of each other but also of the best known upper bound for offline sorting. Specifically, we first prove that if the number of distinct elements (σ= o (n / log n)), then ((H + 1) n + o (n)) comparisons are sufficient, where H is the entropy of the distribution of the elements in S. We then give a simple proof that ((H + 1) n - o (n)) comparisons are necessary in the worst case.