Suppose you have the following three subroutines:
- $\text{max}(A, i, j)$: returns the index of the maximum among the set of consecutive elements $A[i, \dots, j]$ of the array $A$.
- $\text{min}(A, i, j)$: returns the index of the minimum among the set of consecutive elements $A[i, \dots, j]$ of the array $A$.
- $\text{swap}(A, i, j)$: swaps the two elements $A[i]$ and $A[j]$ in the array $A$.
Design an $O(n \log \: n)$ time algorithm which can use only these three subroutines to sort a given array $A = \{A[i]|i = 1, 2, \dots, n\}$ of distinct integers. Assume that the time complexity of the first two subroutines is $O(k)$, where $k = j − i$, and that for the third subroutine is $O(1)$.
