Discrete Mathematics & Theoretical Computer Science |

- 1 Department of Mathematics [Uppsala]

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^{1/2}$, 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^{1/3}$. We also treat some variations, including priority queues and sock-sorting.

Source: HAL:hal-01184796v1

Volume: DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)

Section: Proceedings

Published on: January 1, 2007

Imported on: May 10, 2017

Keywords: Brownian motion,evolution of random strings,sorting algorithm,runs,priority queues,sock-sorting,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

This page has been seen 194 times.

This article's PDF has been downloaded 167 times.