Given a pile of discs of various sizes, the challenge is to write an algorithm that rearranges them from largest (bottom) to smallest (top) by only using pairwise comparisons of the discs
- max(i, j) - and the reverse(i) operation. That is, no swaps, no auxiliary lists.
The input is a list of integer sizes, S1…Sn. A call to reverse(i) reverses discs 1… i as
shown in the image below. The output should be the increasingly ordered list and the
sequence of reverse operations used to achieve the result.