Consider a list of two numbers, and a task: to sort the list in ascending order.
We will assume that only one operation is permitted.
How many comparison-cum-swaps do we need, on a list of two numbers, to sort it in ascending order? Clearly: one. For instance: if the list is , the comparison-cum-swap immediately shows that they are in ascending order, so we are done. Alternatively, if the list is , the comparison-cum-swap immediately shows they are in the wrong order, they are swapped, and then we are done.
Suppose the list contains three elements: for instance, . How many comparison-cum-swaps do we need? One isn’t enough; we’d only be able to consider two of the numbers, and so the third number would have no effect on the final putatively sorted list we produce. What about two?
Two might be enough to verify that a list is sorted, if we’re lucky. Given , we need only observe that and .
However, two is not enough, in general, to sort a list (rather than simply to check whether it is actually sorted). Consider: every comparison-cum-swap leads to at most two possible orderings of some list . So if there are two comparison-cum-swaps, there are at most orderings the procedure yields. But there are in fact six possible correct orderings of the list:
- ,
- ,
- ,
- ,
- , and
- .
So, if there are only two comparison-cum-swaps, we will not be able to obtain the correct result in two of these cases.We can pose the question for a problem of arbitrary size.