“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
– BigO 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 sublists. Make all the elements for the left sublist less than the pivot. The central list has only one element, which is the pivot. Make all the elements on the right sublist 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 sublist (left and right) into three, as in the above step, with each set of three sublists having its own new pivot (of one element sublist), 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 sublists into two halves until each sublist has only one element.
3) Sort pairs of sublists from left to right recursively, including resulting bigger pairs, until the whole list is regained but completely sorted.
This is the natural way to do mergesort, and it does not really give room, for different code segments, for the same purpose as quicksort does.
BigO Notation of O(n), O(n2) and O(n.log(n))
O(n)
Consider the following code:
int sum = 0;
int A[] = {1, 2, 3, 4, 5, 6, 7, 8};
for (int i=0; i<n; i++) {
sum = sum + A[i];
}
printf(«%dn«, sum);
n = 8. The output, the sum is 36. In the forloop, there is one operation that is executed 8 times. In bigO notation, this speed (time complexity) is written as,
Consider the following similar code, where only the odd numbers are added:
int sum = 0;
int A[] = {1, 2, 3, 4, 5, 6, 7, 8};
for (int i=0; i<n; i=i+2) {
sum = sum + A[i];
}
printf(«%dn«, sum);
The output, sum this time, is 16. In the forloop, the one operation is executed 4 times, which is n/2 times. In bigO notation, this speed (time complexity) is still written as O(n). The maximum number of possible operations is what is considered.
O(n^{2})
Consider the following code that adds the matrix of 8by8 numbers:
int sum = 0;
int A[] = {1, 2, 3, 4, 5, 6, 7, 8};
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
sum = sum + A[j];
}
}
printf(«%dn«, sum);
The output, the sum, is 288. In the forloop, there is one operation that is executed 8 X 8 times = 64 times. In bigO notation, this speed (time complexity) is written as,
Consider the following similar code, where only the odd numbers of the matrix are added:
int sum = 0;
int A[] = {1, 2, 3, 4, 5, 6, 7, 8};
for (int i=0; i<n; i=i+2) {
for (int j=0; j<n; j=j+2) {
sum = sum + A[j];
}
}
printf(«%dn«, sum);
The output, sum this time, is 64. In the forloop, the one operation is executed 4 X 4 times = 16 times, which is n^{2}/4 times. This is more than 8 times (more than n times) but less than 64 times (less than n^{2} times). In bigO notation, this speed (time complexity) can still be written as O(n^{2}). 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^{2}), can still be written, as in the following subsection.
O(n.log(n))
Consider the situation of an 8by8 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^{2}).
Now,
24 = 8xlog_{2}(8)
=> 24 = 8xlog_{2}(2^{3})
=> 24 = 8×3
Now compare,
24 = 8xlog_{2}(8)
with
24 = n.log_{2}(n)
For the maximum of n^{2}, when the total number of operations is between n and n^{2}, and around their middle, in bigO notation, this speed (time complexity) is better written as n.log_{2}(n) instead of O(n^{2}).
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_{2}(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_{2}(n), higher than mergesort, assuming a good partition function is used. Many quicksort programs have higher time complexity. The worstcase time complexity for quicksort is O(n^{2}). 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.