Sorting Using Complete Subintervals and
the Maximum Number of Runs in a Randomly Evolving
Sequence

Svante Janson

Department of Mathematics, Uppsala
University, PO Box 480, SE-751~06 Uppsala, Sweden
**AMS Subject Classification: **60C05; 68W40
**Keywords: **sorting algorithm,
runs, priority queues, sock-sorting, evolution of
random strings, Brownian motion

svante.janson@math.uu.se

Annals of Combinatorics 12 (4) pp.413-443 December, 2008

Abstract:

We study the space
requirements of a sorting algorithm where only items
that at the end will be adjacent are kept together.
This is equivalent to the following combinatorial
problem: Consider a string of fixed length $n$ that
starts as a string of $0$'s, and then evolves by
changing each $0$ to $1$, with the $n$ changes done in
random order. What is the maximal number of runs of
$1$'s? We give asymptotic results for the distribution
and mean. It turns out that, as in many problems
involving a maximum, the maximum is asymptotically
normal, with fluctuations of order $n\qq$, and to the
first order well approximated by the number of runs at
the instance when the expectation is maximized, in this
case when half the elements have changed to $1$; there
is also a second order term of order $n\qqq$. We also
treat some variations, including priority queues and
sock-sorting. The proofs use methods originally
developed for random graphs.
References:

1. G. af H¨allstr¨om, Ein lineares Inselproblem der kombinatorischen Wahr-schein-lich-keitsrech- nung, Ann. Acad. Sci. Fennicae. Ser. A. I. Math.-Phys. 1952 (123) (1952) 9 pp.

2. A.D. Barbour, A note on the maximum size of a closed epidemic, J. R. Stat. Soc. Ser. B 37 (3) (1975) 459-460.

3. A.D. Barbour, Brownian motion and a sharply curved boundary, Adv. in Appl. Probab. 13 (4) (1981) 736-750.

4. P. Billingsley, Convergence of Probability Measures, John Wiley & Sons, New York- London-Sydney, 1968.

5. H.E. Daniels, The maximum size of a closed epidemic, Adv. in Appl. Probab. 6 (1974) 607-621.

6. H.E. Daniels, The maximum of a Gaussian process whose mean path has a maximum, with an application to the strength of bundles of bres, Adv. in Appl. Probab. 21 (2) (1989) 315- 333.

7. H.E. Daniels and T.H.R. Skyrme, The maximum of a random walk whose mean path has a maximum, Adv. in Appl. Probab. 17 (1) (1985) 85-99.

8. P. Flajolet, J. Franc¸on, and J. Vuillemin, Sequence of operations analysis for dynamic data structures, J. Algorithms 1 (2) (1980) 111-141.

9. P. Flajolet, C. Puech, and J. Vuillemin, The analysis of simple list structures, Inform. Sci. 38 (2) (1986) 121-146.

10. P. Groeneboom, Brownian motion with a parabolic drift and Airy functions, Probab. Theory Related Fields 81 (1) (1989) 79-109.

11. A. Gut, Probability: A Graduate Course, Springer, New York, 2005.

12. J. Jacod and A.N. Shiryaev, Limit Theorems for Stochastic Processes, Springer-Verlag, Berlin, 1987.

13. S. Janson, A functional limit theorem for random graphs with applications to subgraph count statistics, Random Structures Algorithms 1 (1) (1990) 15-37.

14. S. Janson, Orthogonal decompositions and dunctional limit theorems for random graph statistics, Mem. Amer. Math. Soc. 111 (534) (1994) vi+78 pp.

15. S. Janson, Functional limit theorems for multitype branching processes and generalized P´olya urns, Stochastic Process. Appl. 110 (2) (2004) 177-245.

16. O. Kallenberg, Foundations of Modern Probability, 2nd Ed., Springer-Verlag, New York, 2002.

17. C.M. Kenyon and J.S. Vitter, Maximum queue size and hashing with lazy deletion, Algorithmica 6 (4) (1991) 597-619.

18. W.V. Li and G. Pritchard, A central limit theorem for the sock-sorting problem, In: High Dimensional Probability, Progr. Probab., Vol. 43, Birkh¨auser, Basel, (1998) pp. 245-248.

19. G. Louchard, Random walks, Gaussian processes and list structures, Theoret. Comput. Sci. 53 (1) (1987) 99-124.

20. G. Louchard, Large nite population queueing systems part I: the innite server model, Comm. Statist. Stochastic Models 4 (3) (1988) 473-505.

21. G. Louchard, C. Kenyon, and R. Schott, Data structures' maxima, SIAM J. Comput. 26 (4) (1997) 1006-1042.

22. A.M. Mood, The distribution theory of runs, Ann. Math. Statistics 11 (1940) 367-392.

23. D. Steinsaltz, Random time changes for sock-sorting and other stochastic process limit theorems, Electron. J. Probab. 4 (1999) paper 14.

24. W.L. Stevens, Distribution of groups in a sequence of alternatives, Annals of Eugenics 9 (1939) 10-17.

25. C.J. Van Wyk and J.S. Vitter, The complexity of hashing with lazy deletion, Algorithmica 1 (1986) 17-29.