Need higher performance for three-way quick sort

Question

I'm currently trying to implement a three partition quick sort. The below code works fine but does not run in sufficiently enough time. I'm new to data structures, algorithms, and "in depth" programming in general, so my attempts to fiddle around with it to get it to work in less time have largely come to nothing. (Memory performance is fine.)

My intuition is to alter the pivot, but I worry that it wouldn't be a three-way quick sort, then.

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

using std::vector;
using std::swap;


int partition3(vector<int> &a, int l, int r) {

    int x = a[l]; 
    int j = l;
    int k = r;
    int i = l+1; 

    while (i <= k) {
        if (a[i] < x) {
          swap(a[i],a[j]);
          j++; 
          i++;
        }
        else if(a[i] > x) {
            swap(a[i],a[k]);
            k--;
        }
        else {
            i++;
        }
    }

    return j;
}

void randomized_quick_sort(vector<int> &a, int l, int r) {

    if (l >= r) {
        return;
    }

    int k = l + rand() % (r - l + 1);
    swap(a[l], a[k]);

    while (l < r) {
        int m = partition3(a, l, r);
        if ((m-l) < (r-m)) {
            randomized_quick_sort(a, l, m - 1);
            l = m + 1; 
        }
        else {
            randomized_quick_sort(a, m + 1, r);
            r = m - 1;
        }
    }
}

int main() {
    int n; 
    std::cin >> n;
    vector<int> a(n);
    for (size_t i = 0; i < a.size(); ++i) {
        std::cin >> a[i];
    }
    randomized_quick_sort(a, 0, a.size() - 1);
    for (size_t i = 0; i < a.size(); ++i) {
        std::cout << a[i] << ' ';
    }
}

Answer 1

Sorting is quite a complex problem in the real world. Try to look at some efficient implementations, e.g., those provided by implementations of C++ Standard Library. Explore web, read articles, look at discussions, ...

Just some notes:

1. Random number generation is (relatively) expensive, it can slow down quicksort significantly. (However, it can do the opposite for some kind of data as well.)
2. Integer division is (relatively) very expensive, likely more than random number generation.
3. Pure quicksort alone is rarely used in practice. Typically, it is combined with insertion sort, since recursive calls are inefficient for very small partitions (a threshold is usually set somewhere between 8 and 16 elements).
4. To prevent quicksort worst-case complexity, the level of recursion is typically checked and if it crosses some threshold (2 x log_2(n)), the rest of data is soreted with another algorithm (usually heapsort).

Etc...

UPDATE

Two more thoughts:

5. In multi-core/many-core environments, parallel algorithms will likely provide the best speedup for you. But to design a parallel quicksort is anything but easy. The most of the complexity falls on efficient parallel partitioning and load balancing. Libstdc++ Parallel Mode has a nice OpenMP implementation. Or, you can also check my AQsort: https://github.com/DanielLangr/AQsort.
6. To make quicksort more efficient, use tail call elimination/optimization. It considerably reduces the required call stack space.

Answer 2

I see here really solid code.

If you want to keep the algorithm, the best way to speed it up is changing it from recursive to iterative. It will not be a huge boost but it will help, each fucntion call is an overhead that is good to avoid. Manually swaping is also a good choice.

You can also gain some speed avoiding extra memory allocation, so you should try to reuse your variables as much as you can, for example, declare int m out of the while.