학술논문
A bi-partitioned insertion algorithm for sorting
Document Type
Conference
Source
2009 2nd IEEE International Conference on Computer Science and Information Technology Computer Science and Information Technology, 2009. ICCSIT 2009. 2nd IEEE International Conference on. :139-143 Aug, 2009
Subject
Language
Abstract
It is known that insertion sort performs better on almost sorted arrays than other O(n 2 ) sorting algorithms. In this paper we develop a bi-partitioned insertion algorithm for sorting, which out beats all other O(n 2 ) 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.