Lambda in Quicksort C++

Question

I'm writing a quick sort function, with a lambda that randomly selects a pivot for quicksort. When I originally built the function for the sort without a lambda, I benchmarked the function sorting a list of 25,000 strings at 0.012 seconds. now that I have implemented a lambda it is taking the same algorithm 15 seconds to sort the same list no matter how I choose the pivot point. Which I know isn't correct. Here is my code, any ideas why this would impact the performance of this sort so much?

void quickSort (vector <string> &L, function<int(const vector<string> &, 
int,int)> pickPiv, int a, int b){

if (b ==-1){
    b = L.size();
}
const int n = b-a;

if (n<=1){
    return;
    // if list has one element or less then we are done sorting, this breaks the recursion
}
int piv = pickPiv (L,a,b);

swap (L[a],L[piv]);
piv =a;
for (int i =piv+1; i<b; i++){
    if (L[i] < L[piv]){

        swap(L[i],L[piv+1]);
        swap (L[piv],L[piv+1]);
        ++piv;
    }

}

quickSort(L,[](const vector <string> L, int a, int b) -> int {

   //return a;// if we want first element pivoting 
    int randpiv = rand()%(b-a +1)+a;
    return randpiv;
},a, piv);

quickSort(L,[](const vector <string> L, int a, int b) -> int {

   // return a; // if we want first element pivoting 
    int randpiv = rand()%(b-a +1)+a;
    return randpiv;
},piv+1,b);

}

Answer 1

As pointed out in the comments, passing L by value to the pickPivs is very slow, however there are more problems with your code.

You don't need to pass L to the lambdas you are defining at all, as they only operate on a and b.

You shouldn't be using lambda expressions to recurse, instead pass the existing pickPiv

Strongly consider using a std::uniform_int_distribution to pick your random pivot points.

void quickSort (vector <string> &L, function<int(int,int)> pickPiv, int a, int b){

    if (b ==-1){
        b = L.size();
    }
    const int n = b-a;

    if (n<=1){
        return;
    }
    int piv = pickPiv(a, b);

    std::swap(L[a], L[piv]);
    piv =a;
    for (int i = piv+1; i<b; i++){
        if (L[i] < L[piv]){

            swap(L[i], L[piv+1]);
            swap(L[piv], L[piv+1]);
            ++piv;
        }

    }
    quickSort(L, pickPiv, a, piv);
    quickSort(L, pickPiv, piv+1, b);
}

int main(){
    std::random_device rd;  //Will be used to obtain a seed for the random number engine
    std::mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()

    std::vector<int> vec = { 4, 2, 7, 19, 3 };
    quickSort(vec, [&gen](int a, int b){
        std::uniform_int_distribution<> dis(a, b);
        return dis(gen);
    }, 0, -1);
}