Why is In-place QuickSort slower than normal version in C++?

Question

In Xcode of my macOS, I've made a timer test for quicksort.when my element's quantity is like 10, 100. Until I have set an amount like 1000, the running time of my In-place version becomes slower than another version. I'm using C++ to do this test. here is the code of my main function:

    const int sort_size = 100000;
    clock_t begin, end;
    vector<int> vec_1;
    srand((unsigned)time(NULL));
    for (auto i = 0; i < sort_size; ++i) {
        auto r = rand() % sort_size;
        vec_1.push_back(r);
    }
    vector<int> vec_2(vec_1);
    begin = clock();
    auto sort_1 = QuickSort::exec(vec_1);
    end = clock();
    printf("%lfs\n", (double)(end - begin) / CLOCKS_PER_SEC);
    begin = clock();
    auto sort_2 = QuickSort::exec_in_place(vec_2, 0, sort_size - 1);
    end = clock();
    printf("%lfs\n", (double)(end - begin) / CLOCKS_PER_SEC);

Both two functions have used static declaration.

here is the In-place version code:

vector<int> QuickSort::exec_in_place(vector<int> &nums, int begin, int end) {
    if (begin >= end) {
        return nums;
    }
    auto pivot = [=, &nums] () {
        auto pivot_idx = begin + (end - begin) / 2;
        auto pivot_val = nums[pivot_idx], idx_1 = begin;
        std::swap(nums[pivot_idx], nums[end]);
        for (auto idx_2 = begin; idx_2 <= end - 1; ++idx_2) {
            if (nums[idx_2] > pivot_val) continue;
            std::swap(nums[idx_1], nums[idx_2]);
            idx_1++;
        }
        std::swap(nums[idx_1], nums[end]);
        return idx_1;
    }();
    exec_in_place(nums, begin, pivot - 1);
    exec_in_place(nums, pivot + 1, end);
    return nums;
}

I have tried to pull the lambda function out and packaging into another static function, but the result is still the same.

here is my another normal version, it was also used recursive style.

vector<int> QuickSort::exec(const vector<int> &nums) {
    if (nums.size() < 2) {
        return nums;
    }
    auto pivot = nums[0];
    vector<int> smaller;
    vector<int> greater;
    for (auto i = 1; i < nums.size(); ++i) {
        int num = nums.at(i);
        if (num < pivot) {
            smaller.push_back(num);
        } else {
            greater.push_back(num);
        }
    }
    auto smaller_nums = exec(smaller);
    auto greater_nums = exec(greater);
    smaller_nums.push_back(pivot);
    smaller_nums.insert(smaller_nums.end(), greater_nums.begin(), 
    greater_nums.end());
    return smaller_nums;
}

Ever Since I set amount like 1000, 10000, etc. The In-place began to slow down. For example, when the amount equal to 1000, the In-place spend 0.005356sec, but the normal version used 0.001464sec. when the amount reaches like 100k, the In-place version is about 50sec, but the normal version is about 0.5sec. Could someone tell me why？

Sorry for any grammatical mistakes, English is not my native language.

Answer 1

Can't comment but in the the in-place version you don't need the lambda and you don't need to return the vector. Untested, with minimal changes to the original code:

void exec_in_placex(vector<int> &nums, int begin, int end) {
    if (begin >= end) {
        return;
    }

    auto pivot_idx = begin + (end - begin) / 2;
    auto pivot_val = nums[pivot_idx], idx_1 = begin;
    std::swap(nums[pivot_idx], nums[end]);
    for (auto idx_2 = begin; idx_2 <= end - 1; ++idx_2) {
        if (nums[idx_2] > pivot_val) continue;
        std::swap(nums[idx_1], nums[idx_2]);
        idx_1++;
    }
    std::swap(nums[idx_1], nums[end]);
    auto pivot = idx_1;

    exec_in_placex(nums, begin, pivot - 1);
    exec_in_placex(nums, pivot + 1, end);
}