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

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

Here’s a working example:
Ideone

11 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

Leave a Reply

Your email address will not be published.