Sorting by Placement and Shift

Details Sorting by Placement and Shift Sorting by Placement and Shift

2008-09-17

arxiv.org/abs/0809.2957v1

Mathematics

Combinatorics

13 pages, 4 figures, Proceedings of SODA 2009

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Sorting by Placement and Shift does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sorting by Placement and Shift, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sorting by Placement and Shift will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-661847