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
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
Citation: Yangjun Chen and Ruilin Su. “Merge Sort Revisited". Acta Scientific Computer Sciences 4.5 (2022): 49-52.
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.