Almost-sure asymptotic for the number of heaps inside a random sequence

2017/02/21 by Anne-Laure Basdevant, Basdevant, Anne-Laure, Arvind Singh +1
Computer Science · Mathematics · #Algorithms and Data Compression #FOS: Mathematics #Optimization and Search Problems #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1702.06444

openalex publication_date 2017/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the minimum number of heaps required to sort a random sequence using a generalization of Istrate and Bonchis's algorithm (2015). In a previous paper, the authors proved that the expected number of heaps grows logarithmically. In this note, we improve on the previous result by establishing the almost-sure and L 1 convergence.

Related

• Sorting using complete subintervals and the maximum number of runs in a randomly evolving sequence
• Lower bound on the running time of Pop-Stack Sorting on a random permutation
• Heapable Sequences and Subsequences
• Partition into heapable sequences, heap tableaux and a multiset extension of Hammersley's process
• Almost sure asymptotics for the random binary search tree