Why does the quick sort algorithm duration increase when the array has duplicate values?

Question

I am trying to measure the duration for both Merge Sort and Quick Sort functions using std::chrono time calculations and using randomly generated arrays of integers within some range [A, B], the sizes of the arrays vary from 5000 to 100,000 integers.

The goal of my code is to prove that when the method of picking the (pivot) in quick sort is improved, the quick sort function ends up taking less time to process the array than merge sort, the way I pick the pivot is using the random index method to minimize the probability of having a complexity of (n^2), However in some cases which I will describe below, the quick sort ends up taking more time than merge sort and I would like to know why this occurs.

case 1: The range of the numbers in the array is small which increases the probability of having duplicate numbers in the array.

case 2: When I use a local IDE like clion, the quick sort function takes a lot more time than merge sort, however an online compiler like IDEONE.com gives similar results in both sorting algorithms (even when the range of the generated integers is small)

here are the results I got in the mentioned cases(the first row of numbers is merge sort results, the second row is quick sort results):

1-clion results narrow range of numbers (-100, 600)

2-clion results with a wide range of numbers (INT_MIN, INT_MAX)

3-IDEONE results with a narrow range of numbers (-100, 600)

4- IDEONE results with a wide range of numbers (INT_MIN, INT_MAX)

#include <bits/stdc++.h>
#include <chrono>
#include <random>

using namespace std;

mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
int* generateArray(int size)
{
    int* arr = new int[size];
    uniform_int_distribution<> distribution(INT_MIN, INT_MAX);
    for (int i=0; i < size; ++i)
    {
        arr[i] = distribution(gen);
    }
    return arr;
}
void merge(int* leftArr, int nL, int* rightArr, int nR, int* mainArr)
{
    int i=0, j=0, k=0;
    while (i < nL && j < nR)
    {
        if (leftArr[i] < rightArr[j]) { mainArr[k++] = leftArr[i++]; }
        else { mainArr[k++] = rightArr[j++]; }
    }
    while (i < nL){ mainArr[k++] = leftArr[i++]; }
    while (j < nR){ mainArr[k++] = rightArr[j++]; }
}
void mergeSort (int* mainArray, int arrayLength)
{
    if (arrayLength < 2) { return; }
    int mid = arrayLength/2;
    int* leftArray = new int[mid];
    int* rightArray = new int[arrayLength - mid];
    for (int i=0; i<mid; ++i) {leftArray[i] = mainArray[i];}
    for (int i = mid; i<arrayLength; ++i) {rightArray[i - mid] = mainArray[i];}
    mergeSort(leftArray, mid);
    mergeSort(rightArray, arrayLength-mid);
    merge(leftArray, mid, rightArray, arrayLength-mid, mainArray);
    delete[] leftArray;
    delete[] rightArray;
}


int partition (int* arr, int left, int right)
{
    uniform_int_distribution<> distribution(left, right);
    int idx = distribution(gen);
    swap(arr[right], arr[idx]);
    int pivot = arr[right];
    int partitionIndex = left;
    for (int i = left; i < right; ++i)
    {
        if (arr[i] <= pivot)
        {
            swap(arr[i], arr[partitionIndex]);
            partitionIndex++;
        }
    }
    swap(arr[right], arr[partitionIndex]);
    return partitionIndex;
}
void quickSort (int* arr, int left, int right)
{
    if(left < right)
    {
        int partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
}

int main()
{
    vector <long long> mergeDuration;
    vector <long long> quickDuration;
    for (int i = 5000; i<= 100000; i += 5000)
    {
        int* arr = generateArray(i);
        auto startTime = chrono::high_resolution_clock::now();
        quickSort(arr, 0, i - 1);
        auto endTime = chrono::high_resolution_clock::now();
        long long duration = chrono::duration_cast<chrono::milliseconds>(endTime - startTime).count();
        quickDuration.push_back(duration);
        delete[] arr;
    }
    for (int i = 5000; i <= 100000; i += 5000 )
    {
        int* arr = generateArray(i);
        auto startTime = chrono::high_resolution_clock::now();
        mergeSort(arr, i);
        auto endTime = chrono::high_resolution_clock::now();
        long long duration = chrono::duration_cast<chrono::milliseconds>(endTime - startTime).count();
        mergeDuration.push_back(duration);
        delete[] arr;
    }
    for (int i = 0; i<mergeDuration.size(); ++i)
    {
        cout << mergeDuration[i] << " ";
    }
    cout  << endl;
    for (int i = 0; i<quickDuration.size(); ++i)
    {
        cout << quickDuration[i] << " ";
    }
}

Answer 1

Quicksort is known to exhibit poor performance when the input set contains lots of duplicates. The solution is to use three-way partitioning as described on Wikipedia:

Repeated elements

With a partitioning algorithm such as the ones described above (even with one that chooses good pivot values), quicksort exhibits poor performance for inputs that contain many repeated elements. The problem is clearly apparent when all the input elements are equal: at each recursion, the left partition is empty (no input values are less than the pivot), and the right partition has only decreased by one element (the pivot is removed). Consequently, the algorithm takes quadratic time to sort an array of equal values.

To solve this problem (sometimes called the Dutch national flag problem), an alternative linear-time partition routine can be used that separates the values into three groups: values less than the pivot, values equal to the pivot, and values greater than the pivot. ... The values equal to the pivot are already sorted, so only the less-than and greater-than partitions need to be recursively sorted. In pseudocode, the quicksort algorithm becomes

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := pivot(A, lo, hi)
        left, right := partition(A, p, lo, hi)  // note: multiple return values
        quicksort(A, lo, left - 1)
        quicksort(A, right + 1, hi)

The partition algorithm returns indices to the first ('leftmost') and to the last ('rightmost') item of the middle partition. Every item of the partition is equal to p and is therefore sorted. Consequently, the items of the partition need not be included in the recursive calls to quicksort.

The following modified quickSort gives much better results:

pair<int,int> partition(int* arr, int left, int right)
{
    int idx = left + (right - left) / 2;
    int pivot = arr[idx]; // to be improved to median-of-three
    int i = left, j = left, b = right - 1;
    while (j <= b) {
        auto x = arr[j];
        if (x < pivot) {
            swap(arr[i], arr[j]);
            i++;
            j++;
        } else if (x > pivot) {
            swap(arr[j], arr[b]);
            b--;
        } else {
            j++;
        }
    }
    return { i, j };
}
void quickSort(int* arr, int left, int right)
{
    if (left < right)
    {
        pair<int, int> part = partition(arr, left, right);
        quickSort(arr, left, part.first);
        quickSort(arr, part.second, right);
    }
}

Output:

0 1 2 3 4 5 6 7 8 9 11 11 12 13 14 15 16 19 18 19
0 0 0 1 0 1 1 1 1 1 2 3 2 2 2 2 3 3 3 3

0 1 2 3 4 5 6 6 8 8 9 12 11 12 13 14 16 17 18 19
0 0 1 1 1 2 3 3 3 4 4 4 5 6 5 6 7 7 8 8

So, the run with lots of duplicates is now much faster.

Answer 2

Why does the quick sort algorithm duration increase when the array has duplicate values?

This is only true if using Lomuto type partition scheme, where duplicate values cause the splitting to get worse.

If using Hoare partition scheme, the algorithm duration generally decreases when the array has duplicate values, because the splitting gets closer to the ideal case of splitting exactly in half and the improved splitting compensates for the extra swaps on a typical system with memory cache.