Why does this quicksort appear to be faster than std::sort?

Question

Why does it appear that this quicksort algorithm is faster than std::sort? I've checked to make sure it's actually sorting the array. I've also replaced both sorting calls with hollow for loops of the same number of iterations to test the timing benchmark and everything checked out there.

I'm also wondering what adjustments I can make to the quicksort to allow it to recurse more times. Maybe some sort of variable memory management?

#include <iostream>     
#include <vector>       
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <chrono>
using namespace std;
void quickSort(int*, int);
void fillRandom(int*, int,int b2);
int main() {
    //setup arrays
    int size = 100000;
    auto myints = new int[size];
    auto myints2 = new int[size];
    fillRandom(myints, size,10000);
    std::copy(myints, myints + size, myints2);

    //measurement 1
    auto t1 = std::chrono::high_resolution_clock::now();
    quickSort(myints, size);
    auto t2 = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();
    std::cout << endl << "Execution 1 took: "<< duration << endl;

    //measurement 2
    t1 = std::chrono::high_resolution_clock::now();
    std::sort(myints2,myints2+size);
    t2 = std::chrono::high_resolution_clock::now();
    duration = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();
    std::cout << endl << "Execution 2 took: " << duration << endl;


    cout << "finished!";
    return 1;
}
void fillRandom(int* p, int size,int upTo) {
    srand(time(0));
    for (int i = 0;i < size;i++) {
        p[i] = rand() % upTo + 1;
    }
}
void quickSortSwap(int *p1, int*p2) {
    int temp = *p1;
    *p1 = *p2;
    *p2 = temp;

}
void quickSort(int* original, int len) {
    int split = *original;
    int greaterIndex = len - 1;
    int lesserIndex = 1;
    int* currentP;
    //rearrange stuff so smaller is left, bigger is right
    for (int i = 1;i < len;i++) {
        currentP = original + lesserIndex;
        //cout << *currentP << " compared to " << split << endl;
        if (*currentP <= split) {
            lesserIndex++;
        }
        else {
            //cout << "greater: " << *currentP <<endl;
            quickSortSwap(currentP, original + greaterIndex);
            greaterIndex--;
        }
    }

    //uhh, now we switch pivot element with the right most left side element. Adjust our left side length measurement accordingly.
    lesserIndex--;
    quickSortSwap(original, original + lesserIndex);
    greaterIndex++;
    //this point
    if (lesserIndex > 1) {
        quickSort(original, lesserIndex);
    }
    int greater_range = len - greaterIndex;
    if (greater_range > 1) {
        quickSort(original + greaterIndex, greater_range);
    }
}

https://rextester.com/AOPBP48224

Answer 1

Visual Studio's std::sort has some overhead and some optimizations that your program does not. Your program is based on Lomuto partition scheme, while std::sort is a single pivot, 3 partition Hoare like quicksort + insertion sort for small partitions. The 3 partitions are elements < pivot, elements == pivot, elements > pivot. If there are no duplicate values, the 3 partition sort is just some overhead. If there are duplicate values, then as the number of duplicate values increases, Lomuto gets worse, and Hoare or std::sort get better. Try using fillRandom(myints, size,10); and you should see a large performance hit with Lomuto method, and an increase in performance with std::sort().

Visual Studio's std::sort uses median of nine if >= 40 elements, median of 3 for 33 to 39 elements, which reduces the probability of worst case scenarios, and switches to insertion sort for <= 32 elements (this speeds it up). To reduce stack overhead, it uses recursion for the smaller partition, and loops back to handle the larger partition. It has a check to avoid worst case time complexity O(n^2), switching to heap sort if the depth of partitioning ("recursions") becomes excessive. It uses iterators instead of plain pointers, but in release mode, my impression is the iterators are unchecked, and effectively pointers. It also uses a function pointer for less than compare, defaulting to std::less, which I don't know if it get optimized away.