Quicksort is a sorting algorithm whose worst-case running time is O(n2), for an input of size n. Quicksort, in spite of having worse time complexity than Merge Sort which is O(nlogn), it is a better practical choice for sorting. This is because it is remarkably efficiently on average cases, where its time complexity is O(nlogn). It also has an advantage of sorting in-place.
Merge Sort
It is remarkably better than Selection sort, Insertion sort, or Bubble sort. It uses Divide and Conquer approach. Just like any other Divide & Conquer algorithm, Merge sort recursively call the Merge sort method to sort the input data.
It follows the basic paradigm of Divide & Conquer
- Divide the problem into subproblems ie. divide the array into two smaller arrays.
- Conquer the subproblems by solving them recursively or sorting the smaller arrays.
- Combine the solutions of sub problems to get the final solution or merge the intermediary smaller arrays into a single array.
Pseudocode
Let's consider an Array A, where p & r are indices of the elements of the array such that p = 0 and r = Length(A) - 1
Merge-Sort (A, p, r)
if p < r
q = (p+r)/2
Merge-Sort(A, p, q)
Merge-Sort(A, q+1, r)
Merge(A, p, q, r)
Now consider pseudocode for Merge method
Merge (A, p, q, r)
n1 = q - p + 1
n2 = r - (q + 1) + 1 or r - q
Create Arrays L[1...n1+1] & R[1...n2+1]
for i: 1 to n1
do L[i] = A[p+i-1]
for j: 1 to n2
do R[j] = A[q+j]
i = 1, j = 1
for k: p to r
if L[i] <= R[j]
A[k] = L[i]
i = i+1
else A[k] = R[j]
j = j+1
Quick sort
Quicksort like merge sort is also based on Divide-and-Conquer paradigm. Let’s see how:
- Divide or partition the array
A[p..q]
into two subarrays:A[p..q-1]
&A[q+1..r]
such that all the elements of ArrayA[p..q-1]
are smaller thanA[q]
. Also, all the elements of ArrayA[q+1..r]
are greater thanA[q]
. - Conquer or sort the two subarrays
A[p..q-1]
&A[q+1..r]
recursively. - Combine the sorted subarrays in-place which is nothing but the Array
A[p..r]
.
Pseudocode
Let's consider an Array A, where p & r are indices of the elements of the array such that p = 0 and r = Length(A) - 1
Quick-Sort (A, p, r)
if p < r
q = Partition (A, p, r)
Quick-Sort(A, p, q)
Quick-Sort(A, q+1, r)
Now consider pseudocode for Partition method
Partition (A, p, r)
x = A[r] //x is pivot
// i is the partition index such that at any time
// all element to left of i will be less than pivot x.
i = p - 1
for j: p to r-1
if A[j] <= x
i = i + 1
exchange (A[i], A[j]) //Swapping elements
exchange (A[i+1], A[r])
return i+1 //Pivot's index or partition index
Why is Quicksort better?
Now you’ve got the implementation of both the sorting algorithms. You must be able to understand the advantages of Quicksort over Merge sort.
This is a commonly asked question in the interviews that despite of better worst case performance of merge sort, quicksort is considered better than merge sort, especially for a large input. There are certain reasons due to which quicksort is better:
1- Auxiliary Space: Quick sort is an in-place sorting algorithm. In-place sorting means no additional storage space is needed to perform sorting. Merge sort on the other hand requires a temporary array to merge the sorted arrays and hence it is not in-place.
2- Worst case: The worst case of quicksort O(n2)
can be avoided by using randomized quicksort. It can be easily avoided with high probability by choosing the right pivot. Obtaining an average case behaviour by choosing right pivot element makes it improvise the performance and becoming as efficient as Merge sort.
3- Locality of reference: Quicksort in particular exhibits good cache locality and this makes it faster than merge sort in many cases like in virtual memory environment.
4- Tail recursion: QuickSort is tail recursive while Merge sort is not. A tail recursive function is a function where recursive call is the last thing executed by the function. The tail recursive functions are considered better than non tail recursive functions as tail-recursion can be optimized by compiler.
Here’s the C++ implementation for both Quicksort and Mergesort. You could tweak the input to understand both the algorithms..
Code Implementation
//
// main.cpp
// Quicksort and Mergesort
//
// Created by Himanshu on 29/08/21.
//
#include <iostream>
#include <limits.h>
using namespace std;
const int n = 5;
void printArray (int arr[]) {
for (int i=0; i<n; i++) {
cout<<arr[i]<<" ";
}
cout<<endl;
}
int partition (int A[], int p, int r) {
int x = A[r];
int i = p-1;
for (int j=p; j<r; j++) {
if (A[j] <= x) {
i++;
swap(A[i], A[j]);
}
}
swap(A[r], A[i+1]);
return (i+1);
}
void quicksort (int A[], int p, int r) {
if (p < r) {
int q = partition(A, p, r);
cout<<"Pivot: "<<A[q]<<endl;
cout<<"New array after partition"<<endl;
printArray(A);
quicksort(A, p, q-1);
quicksort(A, q+1, r);
}
}
void merge (int A[], int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
int L[n1 + 1], R[n2 + 1];
//Adding element from 0 to q, to L array
for (int i=0; i<n1; i++) {
L[i] = A[p+i];
}
//Adding element from q+1 to r, to R array
for (int j=0; j<n2; j++) {
R[j] = A[q+j+1];
}
L[n1] = INT_MAX;
R[n2] = INT_MAX;
int i=0, j=0;
for (int k=p; k<=r; k++) {
if (L[i] <= R[j]) {
A[k] = L[i];
i = i+1;
} else {
A[k] = R[j];
j = j+1;
}
}
}
void mergesort (int A[], int p, int r) {
if (p < r) {
int q = (p+r)/2;
mergesort(A, p, q);
mergesort(A, q+1, r);
merge(A, p, q, r);
cout<<"New array after merge"<<endl;
printArray(A);
}
}
int main() {
int A[n] = {11, 2, 90, 57, 13};
int B[n] = {11, 2, 90, 57, 13};
cout<<"Initial Array:"<<endl<<endl;
printArray(A);
cout<<endl;
cout<<"-------Quicksort-------"<<endl<<endl;
quicksort(A, 0, n-1);
cout<<"-----------------------"<<endl;
cout<<"Initial Array:"<<endl<<endl;
printArray(B);
cout<<endl;
cout<<"-------Mergesort-------"<<endl<<endl;
mergesort(B, 0, n-1);
return 0;
}
Output
Initial Array:
11 2 90 57 13
-------Quicksort-------
Pivot: 13
New array after partition
11 2 13 57 90
Pivot: 2
New array after partition
2 11 13 57 90
Pivot: 90
New array after partition
2 11 13 57 90
-----------------------
Initial Array:
11 2 90 57 13
-------Mergesort-------
New array after merge
2 11 90 57 13
New array after merge
2 11 90 57 13
New array after merge
2 11 90 13 57
New array after merge
2 11 13 57 90
Quicksort: Notice how after each iteration, pivot is placed at its correct position.
Mergesort: Notice how after each iteration, individual subarrays are sorted and then merged.
Here’s a working example: Ideone
33 thoughts on “Why is Quicksort better than Merge Sort? [Divide & Conquer]”
I am curious to find out what blog platform you happen to be utilizing?
I’m experiencing some small security issues with
my latest website and I’d like to find something more secure.
Do you have any suggestions?
I always used to study paragraph in news papers but now as I am a user of internet therefore from now I am using net for posts, thanks to web.
สล็อต เว็บใหญ่ อันดับ
1,เว็บใหญ่สล็อต,เว็บ
ใหญ่ สล็อต,เกมสล็อตเว็บใหญ่,สล็อต
เว็บ ใหญ่ ที่สุด pg,สล็อต เว็บ ใหญ่ อันดับ 1,เกมสล็อตอันดับ 1,สล็อต เว็บใหญ่,เว็บสล็อตใหญ่ที่สุด,สล็อตเว็บใหญ่ pg,เว็บสล็อต ที่ มี คน เล่น มาก ที่สุด,สล็อตเว็บใหญ่ที่สุดในโลก,เว็บ สล็อต ใหญ่ ๆ,สล็อต
เว็บ ใหญ่ เว็บ ตรง,สล็อตเว็บใหญ่ที่สุด
When someone writes an post he/she retains the idea of a user
in his/her mind that how a user can know it. Therefore that’s why this
piece of writing is outstdanding. Thanks!
I am extremely impressed with your writing skills and also with the layout on your blog. Is this a paid theme or did you modify it yourself? Either way keep up the excellent quality writing, it’s rare to see a great blog like this one today.
Thank you
Your method of explaining everything in this post is genuinely pleasant, all be able to effortlessly understand it, Thanks a lot.
Thanks
Fantastic goods from you, man. I’ve understand your stuff previous to and you’re just too fantastic. I really like what you’ve acquired here, really like what you are stating and the way in which you say it. You make it entertaining and you still care for to keep it smart. I can not wait to read far more from you. This is really a terrific site.
Thank you @claudedoolittle
Do you mind if I quote a couple of your posts as long as I provide credit and sources back to your blog? My website is in the very same niche as yours and my users would certainly benefit from some of the information you present here. Please let me know if this alright with you. Regards!
It’s okay
Great blog here! Also your web site loads up fast! What host are you using? Can I get your affiliate link to your host? I wish my website loaded up as fast as yours lol
Terrific work! This is the type of information that should be shared around the internet. Disgrace on the search engines for now not positioning this publish higher! Come on over and consult with my site . Thank you =)
Thanks for encouraging words!!
Keep on writing, great job!
Glad you liked
It’s amazing for me to have a site, which is beneficial in support of my experience.
thanks admin https://magikloans.com/contactez-nous/
I was suggested this blog by my cousin. I am not sure whether this post is written by him
as no one else know such detailed about my difficulty.
You’re amazing! Thanks! https://storium.com/user/ikgn758eruv
Thank you
This text is invaluable. How can I find out more?
Thanks
order that I may subscribe.
terima kasih telah berbagi informasi Mas, senang sekali rasanya membaca tulisan2 di blog ini, saya merasa bertambah wawasan semoga selalu di beri kesehatan dan sukses selalu..
Thanks.|
you’re welcome!!
Way cool! Some extremely valid points! I appreciate you writing this write-up and the rest of the website is also really good. http://residencechrist-roi.com/blog/
I am regular reader, how are you everybody?
This paragraph posted at this website is truly pleasant.
Thank you
I visit everyday a few web sites and websites to read articles or reviews, however this webpage gives quality based articles.
Have a look at my web page :: Vern
Thanks Vern!
I?ll immediately {take
education reviewer
Here is my blog post – cfa Practice test
ICE 2010
Also visit my web site – http://epipe.Us