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

Quicksort is a sorting algorithm whose worst-case running time is O(n²), for an input of size n. Quicksort, despite having worse time complexity than Merge Sort which is O(nlogn), 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
 

Time Complexity Analysis of Merge Sort

To analyze the time complexity, we use the divide-and-conquer technique that merge sort uses:

• Divide: Splitting the array takes O(1) time as it is simply dividing the index range in half.
• Conquer: Sorting and merging the two halves are recursive operations, so the time complexity of this step depends on the size of the subarrays.
• Combine: Merging two sorted subarrays of length n/2 takes O(n) time, where n is the size of the current subarray.

Now, let’s denote: T(n) – The time complexity of Merge Sort for an array of size n. The recurrence relation for Merge Sort is:

Explanation

• 2T(n/2): The algorithm recursively sorts two halves of the array, each of size n/2.
• O(n): The time taken to merge these two halves back together.

To deduce the time complexity, we’ll use substitution and solve the recurrence step by step:

Substituting T(n/2) into the equation: T(n) = 2T(n/2) + n :

Substituting this back into T(n)

Similarly, we can generalize:

Here:

• 2^k : The number of subproblems at the k-th level.
• n/2^k : The size of each subproblem at the k-th level.
• kn: The sum of all the merging steps from levels 0 to k−1.

This will continue until n = 2^k or subproblem’s size (n/2^k) becomes 1 i.e.

until k = \log_2(n) .

Thus, substituting k = \log_2(n) into the generalized form:

Here, T(1) is constant and for large values of n,

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