A select and insert sorting algorithm (Q1115197)

A general sorting algorithm, having the well known \(O(n^ 2)\) algorithms Straight Insertion Sort and Selection Sort as special cases, is described. This algorithm is analyzed in the case that certain choices in the algorithm are done randomly, and this yields an algorithm that has an average complexity of \(O(n^{1.5})\) and a worst case complexity of \(O(n^ 2)\). However, making random choices (by some random number generator) is time consuming, and a simple ``quasi-random'' scheme is therefore implemented. Test runs indicate that also this version has average complexity of \(O(n^{1.5})\), and it even seems to perform better than the version using real random choices (even if we disregard the time used for the random choices). This version also needs very little administrative overhead, and it therefore compares favourably to many other sorting algorithms for small and medium sized arrays.