Asra Aslam
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.
- A. Andersson and S. Nilsson. A new efficient radix sort. In Foundations of Comp. Sc., 1994 Proc., 35th Annual Symp on, pages 714--721. IEEE, 1994. Google Scholar
Digital Library
- M. A. Bender, M. Farach-Colton, and M. A. Mosteiro. Insertion sort is O(n log n). Theory of Computing Systems, 39(3):391--397, 2006. Google ScholarDigital Library
- K. Bowers. Accelerating a particle-in-cell simulation using a hybrid counting sort. Journal of Computational Physics, 173(2):393--411, 2001. Google ScholarDigital Library
- R. Cole. Parallel merge sort. SIAM Journal on Computing, 17(4):770--785, 1988. Google ScholarDigital Library
- C. R. Cook and D. J. Kim. Best sorting algorithm for nearly sorted lists. Communications of the ACM, 23(11):620--624, 1980. Google ScholarDigital Library
- T. H. Cormen. Intro. to algorithms. MIT press, 2009.Google Scholar
- H. B. Demuth. Electronic data sorting. Dept of Electrical Engg, Stanford Univ., 1956.Google Scholar
- R. Edjlal, A. Edjlal, and T. Moradi. A sort implementation comparing with bubble sort and selection sort. In 3rd Int Conf Comp Research Dev (ICCRD), volume 4, pages 380--381. IEEE, 2011.Google ScholarCross Ref
- J. Lee, H. Roh, and S. Park. External mergesort for flash-based solid state drives. Computers, IEEE Transactions on, PP(99):1--1, 2015. Google ScholarDigital Library
- S. Lipschutz. Schaum's Outline of Data Structure. McGraw-Hill, Inc., 1987. Google ScholarDigital Library
- F. Liu, M.-C. Huang, X.-H. Liu, and E.-H. Wu. Efficient depth peeling via bucket sort. In Proc. of the Conf. on High Performance Graphics, pages 51--57. ACM, 2009. Google ScholarDigital Library
- Y. Liu and Y. Yang. Quick-merge sort algorithm based on multi-core linux. In Proc Int Conf Mechatronic Sc, Electric Engg and Comp (MEC), pages 1578--1583. IEEE, 2013.Google Scholar
- W. Min. Analysis on bubble sort algorithm optimization. In Int Forum Info Tech Appl (IFITA), volume 1, pages 208--211. IEEE, 2010. Google ScholarDigital Library
- S. Ruggieri. Efficient c4. 5. IEEE Trans Knowledge Data Engg, 14(2):438--444, 2002. Google ScholarDigital Library
- R. T. Smythe and J. Wellner. Stochastic analysis of shell sort. Algorithmica, 31(3):442--457, 2001.Google ScholarCross Ref
- W. Xiang. Analysis of the time complexity of quick sort algorithm. In Int Conf Info Management, Innovation Management and Ind Engg (ICIII), volume 1, pages 408--410. IEEE, 2011. Google ScholarDigital Library
- Y. Yang, P. Yu, and Y. Gan. Experimental study on the five sort algorithms. In Mechanic Automation and Control Engg (MACE), 2011 Second Int. Conf. on, pages 1314--1317. IEEE, 2011.Google ScholarCross Ref
- Non-Partitioning Merge-Sort: Performance Enhancement by Elimination of Division in Divide-and-Conquer Algorithm
Recommendations
Comparing Four Important Sorting Algorithms Based on Their Time Complexity
ACAI '19: Proceedings of the 2019 2nd International Conference on Algorithms, Computing and Artificial IntelligenceTime complexity and memory complexity are significant for all algorithms, especially sorting algorithms. Using the right sorting algorithm for our data can possibly decrease time and memory usage. The sorting problem has attracted a great deal of ...
RVA Sorting Based On Bubble & Quick Sort Technique
ICTCS '14: Proceedings of the 2014 International Conference on Information and Communication Technology for Competitive StrategiesIn the new era of computer science, sorting algorithm is an efficient algorithm which performs an important task that place elements of a list in some order or arrange a set of items into a specific order. Sorting data has been developed to arrange the ...
A top down approach to sorting
Proceedings of the 12th SIGCSE symposium on Computer science educationA top-down approach is presented for the derivation of, and corresponding exposition of sorting algorithms. Work done in automatic program synthesis has produced interesting results about sorting algorithms which suggest this approach. In particular ...
Comments