Multi-way insertion sort
Shenghua Li · Journal of Hubei University · 2008
For the traditional straight insertion sort which runs in O(n2) time,a multi-way insertion sort is proposed.The algorithm and its analysis are given.The relation between the number of the ways used in the algorithm and the time complexity is discussed in detail.It shows that the best number of the ways is O(n),and the time complexity is O(n3/2).Finally,the new algorithm is compared with several existing algorithms,from which it can be seen that our algorithm is more effective.Moreover,our idea can also be applied to the binary insertion sort.