Q:

Is it possible to devise a O(n log n) sorting algorithm using these three procedures Max(A, i, j), Min(A, i, j) and Swap(A, i, j) only?

Max(A, i, j) is a procedure that finds the maximum among the elements indexed from i to j of array A.
Min(A, i, j) is a procedure that finds the minimum among the elements indexed from i to j of array A.
Swap(A, i, j) is a procedure that swaps A[i] and A[j] on array A.
The time complexity of Min(A, i, j) and Max(A, i, j) is O(K) where K = j - i.
The time complexity of Swap(A, i, j) is O(1).
Note: This is not a homework problem as I'm a working professional but I have an upcoming entrance exam for Masters and this is one of the previous year's problems.
I can do this in O(n^2) time easily but I'm unable to divide this problem in half size every iteration and use Min, Max, and Swap to build the sorted output to get O(n log n) time complexity. In whichever way, I think it is coming to O(n^2).
I feel the question is incorrect with regard to the time complexity it wants.

A:

Any comparison-based in-place sort can be implemented at its normal complexity using these primitives.  To compare any 2 items, just swap them into positions 0 and 1, call Min(A,0,1), and swap them back.
Heapsort is the obvious choice for a comparison-based in-place sort with guaranteed O(n log n) time.
In heapsort, comparisons are used to find the maximum among mostly-adjacent items, so you can of course optimize your use of Min/Max to require fewer calls than the way mentioned above.

