SelectionSort accomplishes this by bringing to the back of the array the largest element, one by one, in decreasing order. The largest elements are sorted first, and elements are moved a minimum number of times: at most once.
InsertionSort brings the elements to the front of the array, merging the next unsorted element into the sorted front of the array. The frontmost elements are sorted first, and new elements are merged into its proper place one by one, working toward the end of the array. Elements are swapped into place as they are required to move towards the front of the array, until the element is larger than its immediate predecessor in the array.
This sort has the advantage of running extremely quickly on arrays which are already almost sorted. Compare InsertionSort and SelectionSort on the extreme example of sorting an already sorted array. While SelectionSort will sweep the entire array multiple times simply to verify that the array is already correctly ordered, InsertionSort will verify this in a single pass from front to back, noting that each element is properly ordered and immediately move on to the next.
See the code for additional details.
Burton Rosenberg
November 9, 2000