Non-partitioning merge-sort: Performance enhancement by elimination of division in divide-and-conquer algorithm
Aslam, Asra Ansari, Mohd. Samar Varshney, Shikha
Aslam, Asra
Ansari, Mohd. Samar
Varshney, Shikha
Loading...
Repository DOI
Publication Date
2016-03-04
Type
Conference Paper
Downloads
Citation
Aslam, Asra, Ansari, Mohd. Samar, & Varshney, Shikha. (2016). Non-Partitioning Merge-Sort: Performance Enhancement by Elimination of Division in Divide-and-Conquer Algorithm. Paper presented at the Proceedings of the Second International Conference on Information and Communication Technology for Competitive Strategies, Udaipur, India.
Abstract
The importance of a high performance sorting algorithm with low time complexity cannot be over stated. Several benchmark algorithms viz. Bubble Sort, Insertion Sort, Quick Sort, and Merge Sort, etc. have tried to achieve these goals, but with limited success in some scenarios. Newer algorithms like Shell Sort, Bucket Sort, Counting Sort, etc. have their own limitations in terms of category/nature of elements which they can process. The present paper is an attempt to enhance performance of the standard Merge-Sort algorithm by eliminating the partitioning complexity component, thereby resulting in smaller computation times. Both subjective and numerical comparisons are drawn with existing algorithms in terms of time complexity and data sizes, which show the superiority of the proposed algorithm.
Funder
Publisher
ACM
Publisher DOI
10.1145/2905055.2905092
Rights
Attribution-NonCommercial-NoDerivs 3.0 Ireland