Almost-sure asymptotic for the number of heaps inside a random sequence
Anne-Laure Basdevant, Arvind Singh · arXiv (Cornell University) · 2017
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.