Min-max sort
Narayan Murthy · 1987
A simple sorting algorithm which can be considered as a double-ended selection sort is presented. The algorithm, called min-max sort is based on the optimal method for simultaneously finding the smallest and the largest elements in an array [2]. The smallest and the largest elements found are pushed respectively to the left and right of the array, and the process is repeated on the middle portion. The correctness and termination of min-max sort are easily demonstrated through the use of standard loop invariant ideas. The algorithm fits the “hard split/easy join” paradigm of Merritt [1].