Is the direct comparison of adjacent items in the output array guaranteed by the Quicksort algorithm ?
In other words: During the course of the sorting, the Quicksort algorithm makes (k-2)2^k+2 comparisons in the best case scenario and 2^(2k-1)-3*2^(k-1)+1 comparisons in the worst case scenario, when the number of elements to be sorted (N) is expressed as N=2^k-1.
That is a lot of comparisons, but can we be sure that the adjacent elements appearing in the sorted order in the output array "a[ ]", were directly compared at least once, during the course of the algorithm ? Like this:
cmp(a[1], a[2]); cmp(a[2], a[3]); cmp(a[3], a[4]); ... ; cmp(a[N-1], a[N]);
Yes! Consider the tree formed by the various partition operations, with the pivot element for a partition associated with that node. Nodes are increasing in an in-order traversal. For any given non-maximum node, the node immediately after it in the sorted order is either an ancestor (indicating that, when that node was a pivot, this node was compared with it) or a descendant (indicating the converse).
I'm not sure how you'd use this guarantee, but it is there.
More generally, any comparison-based sorting algorithm has this property. Consider two nodes which end up consecutive in the sorted order. At some point they must have been directly compared with each other, because no transitive chain of comparisons could otherwise prove that the left one was less than the right one.
For instance, suppose the sorted order contained the pieces...foo, bar, baz, qux.... It's possible that foo and qux were never compared with each other: they could instead have each been compared with bar or baz, or one each could have been compared with each one and then bar and baz compared with each other. But you know that foo and bar were directly compared, because no other process could have established that the order should have been that one instead of ...bar, foo, baz, qux.... After all, there's no other element to help out.