A bi-partitioned insertion algorithm for sorting
Tarun Tiwari, Sweetesh Singh, Rupesh Srivastava, N V Sudheer Kumar · 2009
It is known that insertion sort performs better on almost sorted arrays than other O(n2) sorting algorithms. In this paper we develop a bi-partitioned insertion algorithm for sorting, which out beats all other O(n2) sorting algorithms in general cases. The graphs of total time taken by different sorting algorithms confirm the superiority of our algorithm over other existing similar algorithms. We also prove the correctness of the algorithm and give a detailed time complexity analysis of the algorithm.