Merge Sort vs. Quicksort: Algorithm Performance Analysis

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:

• Quicksort
• Merge sort
• Heap sort
• Bubble sort
• Selection sort
• Insertion sort
• Everything About Sorting Algorithms
• And many more!

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 << “nnn”;

}

return 0;
}