ADTs, Data Structures, and Problem Solving with C++ 2nd Edition by Larry Nyhoff

Exercise 5

The double-ended selection sort algorithm described in Exercise 4 can be improved by using a more efficient method for determining the smallest and largest elements in a (sub)list. One such algorithm is known as Min-Max Sort.
Consider a list x 1 ,…, x n , where n is even.
1. For i ranging from 1 to n / 2, compare x i with x n + 1 - i and interchange them if x i x n + 1 -i. This establishes a "rainbow pattern" in which x 1 ? x n , x 2 ? x n - 1 , x 3 ? x n - 2 , and so on and guarantees that the smallest element of the list is in the first half of the list and that the largest element is in the second half.
2. Repeat the following for the list x 1 ,…,x n , then for the sublist x 2 ,…, x n - 1 , and so on:
i. Find the smallest element x S in the first half and the largest element in the second half X L , and swap them with the elements in the first and last positions of this (sub)list, respectively.
ii. Restore the rainbow pattern by comparing x S with x n + 1 ? S and x L with x n + 1 ? L , interchanging as necessary.
a. For the following array x , show x after Step 1 is executed, and then after each pass through the loop in Step 2:

b. Write a function to implement this sorting algorithm.