Increasing Time Efficiency of Insertion Sort for the Worst Case Scenario
Surabhi Patel, Moirangthem Dennis Singh and Chethan Sharma. Article: Increasing Time Efficiency of Insertion Sort for the Worst Case Scenario. IJCA Proceedings on International Conference on Information and Communication Technologies ICICT(7):21-23, October 2014. Full text available. BibTeX
@article{key:article,
author = {Surabhi Patel and Moirangthem Dennis Singh and Chethan Sharma},
title = {Article: Increasing Time Efficiency of Insertion Sort for the Worst Case Scenario},
journal = {IJCA Proceedings on International Conference on Information and Communication Technologies},
year = {2014},
volume = {ICICT},
number = {7},
pages = {21-23},
month = {October},
note = {Full text available}
}
Abstract
Insertion sort gives a time complexity of O(n) for the best case. In the worst case where the input is in the descending order fashion, the time complexity is O(n2). In the case of arrays, shifting takes O(n2) while in the case of linked lists comparison comes to O(n2). Here a new way of sorting for the worst case problem is proposed by using arrays as data structure and taking more space. 2n spaces is taken where n is the number of elements and starts the insertion from (n-1)th location of the array. In this proposed technique the time complexity is O(nlogn) as compared to O(n2) in the worst case.
References
- Insertion Sort,http://www. princeton. edu/~achaney/tmve/wiki100k/docs/Insertion_sort. html
- Wang Min, "Analysis on 2-Element Insertion Sort Algorithm", 2010 International Conference On Computer Design And Applications, IEEE Conference Publications, Pages 143-146 , 2010
- Thomas H. Cormen, Charles. E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms:Printice-Hall, Inc. , 2009
- Mark Allen Weiss, Data Structures and Algorithm Analysis in C++: Pearson Addison-Wesley, 2006
- Michael A. Bender, "Insertion Sort is O(nlogn)," Third International Conference on Fun With Algorithms(FUN), Pages 16-23, 2004
- H. W. Thimbleby, "Using Sentinels in Insert Sort," SoftwarePractice and Experience, Volume 19(3), Pages 303–307,1989.