A bi-partitioned insertion algorithm for sorting

It is known that insertion sort performs better on almost sorted arrays than other O(n² ) sorting algorithms. In this paper we develop a bi-partitioned insertion algorithm for sorting, which out beats all other O(n² ) 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.