Acta Scientific Computer Sciences

Research Article Volume 4 Issue 5

Merge Sort Revisited

Yangjun Chen* and Ruilin Su

Department of Applied Computer Science, University of Winnpeg,

*Corresponding Author: Yangjun Chen, Department of Applied Computer Science, University of Winnpeg, Canada.

Received: March 12, 2022; Published: April 29, 2022

Abstract

Merge sort is a sorting technique based on the divide-and-conquer technique. With its worst-case time complexity being O(𝑛 log 𝑛), it is one of the most respected algorithms. However, in practice, Quick sort is almost three times faster than it although the worst-case time complexity of Quick sort is bounded by O(𝑛2), much worse than O(𝑛 log 𝑛) In this paper, we discuss a new algorithm, which improves the merge sort in two ways: (i) cutting down data movements conducted in the merging processes; and (ii) replacing the recursive calls with a series of improved merging operations. Our experiments show that for the randomly generated input sequences, the performance of our algorithm is comparable to the quick sort. But for the sorted or almost sorted input sequences, or reverse sorted input sequences, our algorithm is nearly 5000 times  better than it.

CCS Concepts: Theory of computation → Algorithm design and analysis.

Keywords: Sequences; Merge Sorting; Quick Sorting

References

  1. A Latif., et al. “Enhancing QuickSort Algorithm using a Dynamic Pivot Selection Technique”. Wulfenia 19.10 (2012): 543-552.
  2. TH Cormen., et al. “Introduction to Algorithms”. Third edition (2009).
  3. CAR Hoare. “Quicksort”. The Computer Journal 5 (1962): 10-15.

Citation

Citation: Yangjun Chen and Ruilin Su. β€œMerge Sort Revisited". Acta Scientific Computer Sciences 4.5 (2022): 49-52.

Copyright

Copyright: Β© 2022 Yangjun Chen and Ruilin Su. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.




Metrics

Acceptance rate35%
Acceptance to publication20-30 days

Indexed In




News and Events


  • Certification for Review
    Acta Scientific certifies the Editors/reviewers for their review done towards the assigned articles of the respective journals.
  • Submission Timeline for Upcoming Issue
    The last date for submission of articles for regular Issues is December 25, 2024.
  • Publication Certificate
    Authors will be issued a "Publication Certificate" as a mark of appreciation for publishing their work.
  • Best Article of the Issue
    The Editors will elect one Best Article after each issue release. The authors of this article will be provided with a certificate of "Best Article of the Issue"

Contact US