slow sort
It’s not QuickSort…
Barry Cipra introduced us to another deceptively simple idea that gives rise to challenging questions.
You have cards numbered from 1 to N. The cards are shuffled, and laid out left to right. Sort them by clicking a card that is not in the correct position. The card will move to its correct position. Continue clicking until all the cards are in the right place.
Below is an example with 5 cards.
Maximizing the number of moves
Perhaps you tried to see how few moves it took for you to get the cards back in order. What is the greatest number of moves possible to sort the cards?
Changing the configuration
Let’s add the ability to change the starting configuration. Assuming that you are taking as many moves as possible for a given configuration, what configuration requires the most moves? Is that configuration unique in allowing that many moves?
Changing the number of cards
What can you learn by varying the number of cards?
Is it possible to create a cycle?
Is it possible to find a starting configuration that after some number of moves, you find yourself back in the starting position? It turns out that is not possible, no matter how many cards you use. Can you prove that?
Read more about it…
Sergi Elizalde and Peter Winkler unpack this problem in their arxiv article, Sorting by Placement and Shift.