A Sort, of Sorts
Sorting is one of the most fundamental, and most studied, computational tasks.
The problem is typically to put n items in order, using the power of a Turing machine
or equivalent. The objective is to minimize time, space, number of comparisons,
or (in the parallel case) number of rounds of comparisons. But you do not need the full
power of a Turing machine to do it. How meager can your computing resources be
to be able to sort? Would you believe three LIFO stacks and no memory? Here, we raise
the question by asking you to design algorithms to sort playing cards. But be wary.
The three problems here, the first of which was communicated to me decades ago
by the brilliant mathematician John H. Conway of Princeton University, are
trickier than they look, and allegedly froze one victim in his chair for six hours.
DOI: 10.1145/2594482 Peter Winkler
Readers are encouraged to submit prospective puzzles for future columns to firstname.lastname@example.org.
Peter Winkler ( email@example.com) is William Morrill Professor of Mathematics and Computer Science at
Dartmouth College, Hanover, NH.
Copyright held by Author/Owner(s).
You thus need an algorithm
whose moves depend only
on what is seen. It will not
know when to stop, but you
may imagine when the cards
are correctly sorted in the
left place, a bell will ring and
you will be showered with
money. So, can you design
an algorithm that eventually
works, regardless of the cards’
1.You wish to sort hree cards: ace (“ 1”),
deuce (“ 2”), and trey (“ 3”).
There are three places on the
table on which cards can be
stacked, and your objective
is to get them stacked in the
left-most place, with 1 on top,
then 2, then 3 on the bottom.
The cards begin faceup
in arbitrary positions; for
example, they may be exposed
as 1, 2, 3 in the left, center,
and right places, respectively
or 2 over 3 over 1 in the right-hand place, in which case you
see only the 2 on top. At any
time you may take a card from
the top of a stack and place it,
still face up, on top of another
(possibly empty) stack. The
difficulty is you see only the
top card or cards and you have
no memory; for example, if
you started with 1 on top of 2
on the left and 3 in the center
and moved 1 to the top of the
3, you are now looking at 2,
1, blank, and you no longer
know the position of the 3.
2.Same problem but now with n cards,
numbered 1 to n, you wish to
sort in the left position, with
1 on top. There are still only
three positions on the table.
3.Same as the second problem, but now
the middle position can hold
only one card; if you try to put
another on it, you lose.