Non-partitioning merge-sort: Performance enhancement by elimination of division in divide-and-conquer algorithm
View/ Open
Date
2016-03-04Author
Aslam, Asra
Ansari, Mohd. Samar
Varshney, Shikha
Metadata
Show full item recordUsage
This item's downloads: 341 (view details)
Cited 1 times in Scopus (view citations)
Recommended 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.
Published Version
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.