Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
close-icon
Iks white logo

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Iks white logo

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
close
closeAbout usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Merge Sort vs. Quicksort: Algorithm Performance Analysis

Last updated by Abhinav Rawat on Sep 25, 2024 at 11:00 PM | Reading time: 10 minutes

The fast well prepared banner

Attend our Free Webinar on How to Nail Your Next Technical Interview

WEBINAR +LIVE Q&A

How To Nail Your Next Tech Interview

Merge Sort vs. Quicksort: Algorithm Performance Analysis
Hosted By
Ryan Valles
Founder, Interview Kickstart
strategy
Our tried & tested strategy for cracking interviews
prepare list
How FAANG hiring process works
hiring process
The 4 areas you must prepare for
hiring managers
How you can accelerate your learnings

Are you getting ready for your next technical interview? As a software developer, you know how important it is to have a crystal clear understanding of sorting algorithms. They’re a frequent feature in coding interviews! Let’s brush up on your sorting basics.

We have already discussed in depth the difference between quicksort and merge sort. In this article, we’ll help you visualize the difference in performance between quicksort and merge sort. You’ll get a better understanding of when to use quicksort vs. when to use merge sort based on the kind of problem you’re solving. 

We’ve analyzed for the following types of input:

  • Randomly Generated Array
  • Sorted Array (Non-Decreasing Order)
  • Sorted Array (Non-Decreasing Order)
  • Almost Sorted Array
  • Array With Many Repeated Entries

Note: 

  • We have used Hoare’s implementation of quicksort, as it performs better than Lamuto’s implementation on average.
  • We have generated the data for a wide range of inputs, ranging from 2.5 * 105 to 108. We are not experimenting with the smaller-sized arrays as both the algorithms perform really fast on small datasets, and we wouldn’t get comparable data.
  • You can check out the code that we used to recreate the data generation. Just make sure to use -std=c++11, -std=c++14 or -std=c++17 flag while compiling the code. (The code is given at the end of this article).

Randomly Generated Array

First, let’s see how the running time changes for sorting a randomly generated array.

As the graph depicts, quicksort has the edge over merge sort — it is faster compared to merge sort when a randomly generated input array is to be sorted.

Sorted Array (Non-Decreasing Order)

Let’s move on to compare their performance on sorting an already sorted array.

As we can see from the graph, quicksort performs near its worst-case complexity of O(n2) when an already sorted data is used. Merge sort algorithm performs far better for this type of dataset.

Sorted Array (Non-Decreasing Order)

Let’s move on to reverse-sorted arrays.

Similar to sorted data, the quicksort algorithm performs a lot worse than merge sort for reverse-sorted arrays. Merge sort is considerably fast in comparison. 

Almost Sorted Array

Next, we are going to compare the time taken for almost sorted arrays, where around 5% of data points are misplaced.

When the dataset is almost sorted, merge sort is still the preferable choice for sorting. One thing that we can take note of is that in this scenario, quicksort performs a lot better than when the dataset is fully sorted.

Array With Many Repeated Entries

Let’s now take data with many repeated elements for comparing the time taken by both the sorting algorithms. We have taken around 10% unique elements for this test.

The performance of quicksort takes a toll when there are many repeated entries in the dataset. As the graph shows, both the algorithms’ performances were at par with each other when the dataset contained only about 10% unique elements. Still, quicksort has a slight edge. 

Array With All Values Same

Let’s now take test arrays where all values are the same.


Quicksort doesn’t perform at par with merge sort when all the values of the dataset are the same.

Conclusion: Quicksort vs. Merge Sort — Which Is the Faster Algorithm?

The time complexity of merge sort is always O(n log n), while the time complexity of quicksort varies between O(n log n) in the best case to O(n2) in the worst case. Based on the results of our analysis, here’s our conclusion:

  • When to use quicksort: Quicksort performs better in situations where the dataset is random and doesn’t have characteristics like being almost sorted or having a lot of duplicate entries.
  • When to use merge sort: Though merge sort takes a little longer time than quicksort for a random dataset, it does have the advantage of being consistent with respect to the time taken for sorting, no matter the dataset’s characteristics.

Want to Learn More About Sorting Algorithms?

Head to Interview Kickstart’s learn page for more articles on sorting, such as:

Looking for a Tech Interview Prep Coach?


Interview Kickstart offers the best technical interview prep courses that make you a better engineer and help you nail tech interviews.

As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!

For more information on what it takes to prepare for and succeed at FAANG tech interviews, sign up for our free webinar

Code Used

If you want to implement this yourself, here is the code that we have used. Make sure to use one of the C++11, C++14, or C++17 to compile it.

Compile Command Used : g++.exe -Wall -std=gnu++11  -c file_name.cpp

#include <bits/stdc++.h>
using namespace std;

class Timer {
public:
    Timer() : beg_(clock_::now()) {}
    void reset() { beg_ = clock_::now(); }
    double elapsed() { return std::chrono::duration_cast<second_> (clock_::now() - beg_).count(); }

private:
    typedef std::chrono::high_resolution_clock clock_;
    typedef std::chrono::duration<double, std::ratio<1> > second_;
    std::chrono::time_point<clock_> beg_;
} timer;

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int rand_int(int a, int b) {
    return uniform_int_distribution<int>(a, b)(rng);
}

const int int_min = -1e9,
          int_max = +1e9;

const int N = 1e8;

int arr[N], a1[N], a2[N], helper[N];

int partition(int arr[], int low, int high) {
    int randomNumberBetweenLowAndHigh = low + rand() % (high - low);
    swap(arr[low], arr[randomNumberBetweenLowAndHigh]);

    int pivot = arr[low];
    int i = low - 1, j = high + 1;

    while (true) {
        do {
            i++;
        } while (arr[i] < pivot);

        do {
            j--;
        } while (arr[j] > pivot);

        if (i >= j)
            return j;

        swap(arr[i], arr[j]);
    }
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi);
        quickSort(arr, pi + 1, high);
    }
}

void merge(int arr[], int low, int mid, int high) {
    int l1, l2, i;

    for (l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
        if (arr[l1] <= arr[l2])
            helper[i] = arr[l1++];
        else
            helper[i] = arr[l2++];
    }

    while (l1 <= mid)
        helper[i++] = arr[l1++];

    while (l2 <= high)
        helper[i++] = arr[l2++];

    for (i = low; i <= high; i++)
        arr[i] = helper[i];
}

void mergeSort(int arr[], int begin, int end) {
  if (begin >= end)
        return;

    auto m = begin + (end - begin) / 2;
    mergeSort(arr, begin, m);
    mergeSort(arr, m + 1, end);
    merge(arr, begin, m, end);
}

void printarr(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << "\n";
}

void randomArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        arr[i] = rand_int(int_min, int_max);
}

void sortedArrayNonDecreasing(int arr[], int n) {
    randomArray(arr, n);
    sort(arr, arr + n);
}

void sortedArrayNonIncreasing(int arr[], int n) {
    randomArray(arr, n);
    sort(arr, arr + n, greater<int>());
}

void almostSortedArray(int arr[], int n) {
    sortedArrayNonDecreasing(arr, n);
    double percentageMisplaced = 5;
    int m = n / 100.0 * percentageMisplaced / 2;
    for (int i = 0; i < m; i++) {
        int x = rand_int(0, n - 1),
            y = rand_int(0, n - 1);
        swap(arr[x], arr[y]);
    }
}

void arrayWithManyDuplicates(int arr[], int n) {
    double percentageUnique = 10;
    int m = n / 100.0 * percentageUnique;
    randomArray(arr, m);
    for (int i = 0; i < n; i++)
        arr[i] = arr[i % m];
    shuffle(arr, arr + n, rng);
}

void arrayWithOnlyOneUnique(int arr[], int n) {
    arr[0] = rand_int(int_min, int_max);
    for (int i = 0; i < n; i++)
        arr[i] = arr[0];
}

void generateTimes(int n) {

    srand(time(NULL));

    timer.reset();
    quickSort(a1, 0, n - 1);
    double = quickSortTime = timer.elapsed();

    timer.reset();
    mergeSort(a2, 0, n - 1);
    double = mergeSortTime = timer.elapsed();

    cout << "n = ";
    cout << n << '\n';
    cout << fixed << setprecision(3);
    cout << "Quick Sort: ";
    cout << quickSortTime << '\n';
    cout << "Merge Sort: ";
    cout << mergeSortTime << '\n';

    sort(arr, arr + n);
    for (int i = 0; i < n; i++)
        assert(arr[i] == a1[i] && arr[i] == a2[i]);

    // printarr(a1, n);
    // printarr(a2, n);
}

int main() {

    vector<string> t = {"randomArray", "sortedArrayNonDecreasing", "sortedArrayNonIncreasing", "almostSortedArray", "arrayWithManyDuplicates", "arrayWithOnlyOneUnique"};

    vector<int> m = {250000, 500000, 1000000, 2500000, 5000000, 10000000, 25000000, 50000000, 100000000};

    for (string s : t) {

        for (int n : m) {

            if (s == "randomArray")
                randomArray(arr, n);
            if (s == "sortedArrayNonDecreasing")
                sortedArrayNonDecreasing(arr, n);
            if (s == "sortedArrayNonIncreasing")
                sortedArrayNonIncreasing(arr, n);
            if (s == "almostSortedArray")
                almostSortedArray(arr, n);
            if (s == "arrayWithManyDuplicates")
                arrayWithManyDuplicates(arr, n);
            if (s == "arrayWithOnlyOneUnique")
                arrayWithOnlyOneUnique(arr, n);

            for (int i = 0; i < n; i++)
                a1[i] = a2[i] = arr[i];

            // printarr(arr, n);

            cout << s << '\n';
            generateTimes(n);
            cout << '\n';

        }

        cout << "\n\n\n";

    }

    return 0;
}

Last updated on: 
September 25, 2024
Author

Abhinav Rawat

Product Manager @ Interview Kickstart | Ex-upGrad | BITS Pilani. Working with hiring managers from top companies like Meta, Apple, Google, Amazon etc to build structured interview process BootCamps across domains

Attend our Free Webinar on How to Nail Your Next Technical Interview

Register for our webinar

How to Nail your next Technical Interview

1
Enter details
2
Select webinar slot
First Name Required*
Last Name Required*
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

Merge Sort vs. Quicksort: Algorithm Performance Analysis

Worried About Failing Tech Interviews?

Attend our webinar on
"How to nail your next tech interview" and learn

Ryan-image
Hosted By
Ryan Valles
Founder, Interview Kickstart
blue tick
Our tried & tested strategy for cracking interviews
blue tick
How FAANG hiring process works
blue tick
The 4 areas you must prepare for
blue tick
How you can accelerate your learnings
Register for Webinar
entroll-image