International Journal of Computer Applications |
Foundation of Computer Science (FCS), NY, USA |
Volume 183 - Number 31 |
Year of Publication: 2021 |
Authors: Ibtehal Mishal, Rasha AL-Khatib, Razan Hiasat |
10.5120/ijca2021921702 |
Ibtehal Mishal, Rasha AL-Khatib, Razan Hiasat . Comparative Study of Two Divide and Conquer Sorting Algorithms: Modified Quick Sort and Merge Sort. International Journal of Computer Applications. 183, 31 ( Oct 2021), 28-33. DOI=10.5120/ijca2021921702
Divide and conquer is a well-known technique for sorting algorithms. Such include Quick sort and Merge sort sorting algorithms. These two algorithms have been extensively used for sorting. However, discovering the most efficient sorting algorithm among the two has always been a contentious problem. Most of the existing research have compared quick sort and merge sort, this study intends to compare the intelligent Quick Sort algorithm based on a dynamic pivot selection technique “modified quicksort” and the merge sort. Using machine-dependent factors such as computational and employed machine-independent internal/external sorting factors, memory usage, stability, algorithm complexity: best, average, and worst cases. This study intends to contribute to this discussion using both machine-dependent and independent factors. Results obtained revealed that in terms of computational speed using an array of small sizes, the classical Quicksort algorithm is almost fast, meanwhile, the Merge sort algorithm is faster with an array of large sizes, However, modified quicksort is the fastest available option in all sizes. Also, the best case for both merge sort and classical quick sort complexity is O(nlogn), but the modified quicksort best case is O(n) which happened when the array is already sorted while the three sorts are of O(nlogn) average case, and the worst case for classical quicksort is O(