Sorting by placement and shift

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.

REFERENCES

• 1: D. Callan, communication to B. Cipra, 22 August 2007.
• 2: B. Cipra, communication to P. Winkler, 19 February 2008.
• 3: N. Elkies, communicated by J. Buhler, 29 January 2008.
• 4: M. Gardner, Time Travel and Other Mathematical Bewilderments, W. H. Freeman & Co. 1987, p. 76.
• 5: L. Larson, communication to B. Cipra, 17 August 2007.
• 6: B. F. Logan and L. A. Shepp, A variational problem for random Young tableau, Advances in Math. 26 (1975), 206--222.
• 7: T. Prellberg, communication to the authors, 10 September 2008.
• 8: P. Vaderlind, R. K. Guy and L. C. Larson, The Inquisitive Problem Solver, Mathematical Association of America, 2002.
• 9: A. M. Vershik and S. V. Kerov, Asymptotics of the Plancherel measure of the symmetric group and the limiting form of Young tableau, Soviet Math. Dokl. 18 (1977), 527--531.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms