Improving Quick Sort

Quick sort is a very popular algorithm whose runtime at worst case is O(n²) and average case is O(n log₂ n). It is widely known that a comparison-based sorting algorithm cannot run faster than O(n log n), however by creating three partition instead of two we can increase its runtime to O(n log₃ n).

For this algorithm, we will used a randomized quick sort which uses a random element as pivot. The use of this randomized pivot is what makes quick sort runs at average time of O(n log₂ n) instead of O(n²). The algorithm will then put a value based on the pivot which indicates that the elements to the left of the pivot is lesser or equal to the pivot element. However, for a input with repetitions this algorithm perform poorly compared to Merge Sort. So a Dutch mathematician came up with an idea, that we return not just the index of the element lesser than equal to the pivot but the element lesser than and also element greater than the pivot. This algorithm is famously known as the Dutch National Flag algorithm. The algorithm implementation in C++ is given below:

#include <iostream>
#include <vector>
#include <cstdlib>

using std::vector;
using std::swap;
using std::cout;
using std::cin;

vector<long long int> partition3(vector<long long int> &a, long long int l, long long int r) {
    long long int i = l;
    long long int gt = r - 1;
    long long int lt = l;
    long long int v = a.at(l);
    while (i < gt) {
        cout << '\n';
        if (a.at(i) < v) {
            swap(a.at(i), a.at(lt));
            i++;
            lt++;
        }
        else if (a.at(i) > v) {
            swap(a.at(i), a.at(gt));
            gt--;
        }
        else {
            i++;
        }
    }
    return {lt, gt};
}

void randomized_quick_sort(vector<long long int> &a, long long int l, long long int r) {
  if (l >= r) {
    return;
  }

  long long int k = l + rand() % (r - l + 1);
  swap(a[l], a[k]);
  vector<long long int> v = partition3(a, l, r);
  long long int m1 = v[0];
  long long int m2 = v[1];

  randomized_quick_sort(a, l, m1 - 1);
  randomized_quick_sort(a, m2 + 1, r);
}

int main() {
    vector<long long int> v, res;
    long long int n, var;
    cin >> n;
    for (long long int i = 0; i < n; i++) {
        cin >> var;
        v.push_back(var);
    }

    randomized_quick_sort(v, 0, n);

    for (long long int i = 0; i < n; i++) {
      cout << v.at(i) << ' ';
    }
    cout << '\n'
    return 0;
}

FYI, this is how the graph of the algorithm compared to traditional Quick Sort:

It is quite significant improvement in running time not only when handling special cases of repetition but also general cases.