Abstract

Among the comparison-based algorithms, INSERTIONSORT is recognized as one of the fastest methods to sort relatively small data sets, or when the elements are relatively ordered. However, due to not offering good asymptotic complexity in its runtime, it performs very poorly both in the worst case and in the average case for most large data collections. In this article we offer a new sorting algorithm based on orderer block insertions with worst case optimal time. At the cost of an additional memory space of nk words, for any constant k, our algorithm is able to easily transform it into an in-place algorithm with a time of symbolscript in the worst case. Empirically, our method outperforms symbolscript in all the different cases tested, even for small input collections. Furthermore, our experiments show that, for small or large datasets from either of the two main probability distributions-Uniform and Normal; our algorithms also outperform any traditional method like symbolscript symbolscript or symbolscript and even better than the efficient hybrid algorithm symbolscript symbolscript method provided by the GNU C++ Standard Library.