Why is Quicksort better than Merge Sort? [Divide & Conquer]

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

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

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

  2. 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 =)

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

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *