**Quicksort** is a sorting algorithm whose worst-case running time is O(n^{2}), 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**Conquer**the subproblems by solving them recursively**Combine**the solutions of sub problems to get the final solution.

**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 Array A[p..q-1] are smaller than A[q]. Also, all the elements of Array A[q+1..r] are greater than A[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(n^2)`

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

## 34 thoughts on “Why is Quicksort better than Merge Sort? [Divide & Conquer]”

ICE 2010

Also visit my web site – http://epipe.Us

education reviewer

Here is my blog post – cfa Practice test

I?ll immediately {take

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 am regular reader, how are you everybody?

This paragraph posted at this website is truly pleasant.

Thank you

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/

Thanks.|

you’re welcome!!

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..

order that I may subscribe.

This text is invaluable. How can I find out more?

Thanks

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

It’s amazing for me to have a site, which is beneficial in support of my experience.

thanks admin https://magikloans.com/contactez-nous/

Keep on writing, great job!

Glad you liked

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!!

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

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

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

Your method of explaining everything in this post is genuinely pleasant, all be able to effortlessly understand it, Thanks a lot.

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

สล็อต เว็บใหญ่ อันดับ

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 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.

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?