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(𝑛²), 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