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
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:
Note:Â
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.
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.
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.
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.
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.
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.
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:
Head to Interview Kickstart’s learn page for more articles on sorting, such as:
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.
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;
}
Time Zone:
Get your enrollment process started by registering for a Pre-enrollment Webinar with one of our Founders.
The 11 Neural “Power Patterns” For Solving Any FAANG Interview Problem 12.5X Faster Than 99.8% OF Applicants
The 2 “Magic Questions” That Reveal Whether You’re Good Enough To Receive A Lucrative Big Tech Offer
The “Instant Income Multiplier” That 2-3X’s Your Current Tech Salary
The 11 Neural “Power Patterns” For Solving Any FAANG Interview Problem 12.5X Faster Than 99.8% OF Applicants
The 2 “Magic Questions” That Reveal Whether You’re Good Enough To Receive A Lucrative Big Tech Offer
The “Instant Income Multiplier” That 2-3X’s Your Current Tech Salary
Just drop your name and email so we can send your Power Patterns PDF straight to your inbox. No Spam!
By sharing your contact details, you agree to our privacy policy.
Time Zone: Asia/Dhaka
We’ve sent the Power Patterns PDF to your inbox — it should arrive in the next 30 seconds.
📩 Can’t find it? Check your promotions or spam folder — and mark us as safe so you don’t miss future insights.
We’re hosting a private session where FAANG insiders walk through how they actually use these Power Patterns to crack interviews — and what sets top performers apart.
🎯 If you liked the PDF, you’ll love what we’re sharing next.
Time Zone:
