DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Andrew Baxter, Rutgers University, baxter{at} math [dot] rutgers [dot] edu

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: A greedy sorting algorithm

Speaker: Sergi Elizalde, Dartmouth College

Date: Thursday, February 18, 2010 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

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. However, it is not obvious that this algorithm necessarily terminates.

We show that in fact the algorithm terminates after at most 2n-1-1 steps in the worst case, and that there are super-exponentially many permutations for which this exact bound can be achieved. The proof involves a curious symmetrical binary representation.

This is joint work with Peter Winkler.