“The aim of this article is to give the similarities and differences between Quick Sort and Merge Sort. The article “Quick Sort in C,” or a similar title, has already been written for linuxhint.com/. The title can be typed in the search box of the linuxhint.com home page to reach the article. Another article, “Merge Sort in C,” or a similar title, has already been written for linuxhint.com/. The title can be typed in the search box of the linuxhint.com home page to reach the article. The reader is advised to be referring to those two articles while he/she reads this one.

Quick Sort is a sorting algorithm. Merge Sort is another sorting Algorithm. The code for the two articles mentioned above is written in C. Code for this article is also written in C. The reader should be aware of that. Sort ascending is considered for both sorting algorithms in this article.”

Article Content

– Introduction – see above
– Algorithms for Quick Sort and Merge Sort
– Big-O Notation of O(n), O(n2), and O(n.log(n))
– Comparing Quick Sort and Merge Sort
– Conclusion

Algorithms for Quick Sort and Merge Sort
Algorithm for Quicksort

1) If there is only one or no element in the list, then return. One element means that the list is already sorted. Zero element means that there is nothing to sort.
2) With an intelligent guess, pick a suitable element in the list as a pivot.
3) Partition (divide) the list into three sub-lists. Make all the elements for the left sub-list less than the pivot. The central list has only one element, which is the pivot. Make all the elements on the right sub-list greater than the pivot. By putting elements on the left that are less than the pivot, and elements on the right that are greater than the pivot, without pure sorting, that is already some sorting (in a broad sense).
4) Recursively divide each sub-list (left and right) into three, as in the above step, with each set of three sub-lists having its own new pivot (of one element sub-list), until the whole given list is perfectly sorted.

There are different coding forms for step 2. A better coding form will lead to faster complete sorting.
There are different coding forms for step 3. A better coding form will lead to faster complete sorting.

Algorithm for Mergesort

1) If there is only one or no element in the list, then return. One element means that the list is already sorted. Zero element means that there is nothing to sort.
2) Recursively divide the list and its sub-lists into two halves until each sub-list has only one element.
3) Sort pairs of sub-lists from left to right recursively, including resulting bigger pairs, until the whole list is regained but completely sorted.

This is the normal way to do mergesort, and it does not really give room, for different code segments, for the same purpose as quicksort does.

Big-O Notation of O(n), O(n2) and O(n.log(n))

O(n)
Consider the following code:

n = 8. The output, the sum is 36. In the for-loop, there is one operation that is executed 8 times. In big-O notation, this speed (time complexity) is written as,

Consider the following similar code, where only the odd numbers are added:

The output, sum this time, is 16. In the for-loop, the one operation is executed 4 times, which is n/2 times. In big-O notation, this speed (time complexity) is still written as O(n). The maximum number of possible operations is what is considered.

O(n²)

Consider the following code that adds the matrix of 8-by-8 numbers:

The output, the sum, is 288. In the for-loop, there is one operation that is executed 8 X 8 times = 64 times. In big-O notation, this speed (time complexity) is written as,

Consider the following similar code, where only the odd numbers of the matrix are added:

The output, sum this time, is 64. In the for-loop, the one operation is executed 4 X 4 times = 16 times, which is n²/4 times. This is more than 8 times (more than n times) but less than 64 times (less than n² times). In big-O notation, this speed (time complexity) can still be written as O(n²). The maximum number of possible operations is what is considered.

Here, do not confuse the sum, 64, and the number of operations, 16. This case of 16 operations, between 8 (n) and 64 (n²), can still be written, as in the following subsection.

O(n.log(n))

Consider the situation of an 8-by-8 matrix, where the total number of operations is 24. 24 can be seen as being roughly around the middle, between 8 (n) and 64 (n²).

Now,

24 = 8xlog₂(8)
=> 24 = 8xlog₂(2³)
=> 24 = 8×3

Now compare,

24 = 8xlog₂(8)
with
24 = n.log₂(n)

For the maximum of n², when the total number of operations is between n and n², and around their middle, in big-O notation, this speed (time complexity) is better written as n.log₂(n) instead of O(n²).

Comparing Quick Sort and Merge Sort
Number of Steps in Algorithm

From above, quicksort has 4 steps in its algorithm, while mergesort has 3 steps in its algorithm.

Different Ways of Coding

Quick Sort has different ways of coding, while merge Sort has only one main way of coding.

Time Complexity

The time complexity for mergesort is n.log₂(n). Its speed is comparable with that of the sort function of the C++ library used for commercial purposes.

When the median pivot function is used for quicksort, the time complexity is approximately 1.188n.log₂(n), higher than mergesort, assuming a good partition function is used. Many quicksort programs have higher time complexity. The worst-case time complexity for quicksort is O(n²). However, if the quicksort program is well coded with very good code segments, it would beat mergesort in speed.

Conclusion

Quicksort normally runs slower than mergesort.