Sorting by Placement and Shift TeX Export

@article{citeulike:3288121, abstract = {In sorting situations where the final destination of each item is known, it is natural to repeatedly choose items and place them where they belong, allowing the intervening items to shift by one to make room. (In fact, a special case of this algorithm is commonly used to hand-sort files.) However, it is not obvious that this algorithm necessarily terminates. We show that in fact the algorithm terminates after at most \$2^{n-1}-1\$ steps in the worst case (confirming a conjecture of L. Larson), and that there are super-exponentially many permutations for which this exact bound can be achieved. The proof involves a curious symmetrical binary representation.}, archivePrefix = {arXiv}, author = {Elizalde, Sergi and Winkler, Peter}, citeulike-article-id = {3288121}, citeulike-linkout-0 = {http://arxiv.org/abs/0809.2957}, citeulike-linkout-1 = {http://arxiv.org/pdf/0809.2957}, eprint = {0809.2957}, keywords = {algorithms, combinatorics, fun, mathematics}, month = {Sep}, posted-at = {2008-09-18 16:37:32}, priority = {2}, title = {Sorting by Placement and Shift}, url = {http://arxiv.org/abs/0809.2957}, year = {2008} }

TY - JOUR ID - citeulike:3288121 L3 - citeulike-article-id:3288121 N2 - In sorting situations where the final destination of each item is known, it is natural to repeatedly choose items and place them where they belong, allowing the intervening items to shift by one to make room. (In fact, a special case of this algorithm is commonly used to hand-sort files.) However, it is not obvious that this algorithm necessarily terminates. We show that in fact the algorithm terminates after at most $2^{n-1}-1$ steps in the worst case (confirming a conjecture of L. Larson), and that there are super-exponentially many permutations for which this exact bound can be achieved. The proof involves a curious symmetrical binary representation. TI - Sorting by Placement and Shift KW - algorithms KW - combinatorics KW - fun KW - mathematics AU - Elizalde, Sergi AU - Winkler, Peter PY - 2008/Sep/17/ UR - http://arxiv.org/abs/0809.2957 ER -