title: Why is In-place QuickSort slower than normal version in C++?
body: <p>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:</p>
  
  <pre><code>    const int sort_size = 100000;
      clock_t begin, end;
      vector&lt;int&gt; vec_1;
      srand((unsigned)time(NULL));
      for (auto i = 0; i &lt; sort_size; ++i) {
          auto r = rand() % sort_size;
          vec_1.push_back(r);
      }
      vector&lt;int&gt; 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);
  </code></pre>
  
  <p>Both two functions have used static declaration.</p>
  
  <p>here is the In-place version code:</p>
  
  <pre><code>vector&lt;int&gt; QuickSort::exec_in_place(vector&lt;int&gt; &amp;nums, int begin, int end) {
      if (begin &gt;= end) {
          return nums;
      }
      auto pivot = [=, &amp;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 &lt;= end - 1; ++idx_2) {
              if (nums[idx_2] &gt; 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;
  }
  </code></pre>
  
  <p>I have tried to pull the lambda function out and packaging into another static function, but the result is still the same.</p>
  
  <p>here is my another normal version, it was also used recursive style.</p>
  
  <pre><code>vector&lt;int&gt; QuickSort::exec(const vector&lt;int&gt; &amp;nums) {
      if (nums.size() &lt; 2) {
          return nums;
      }
      auto pivot = nums[0];
      vector&lt;int&gt; smaller;
      vector&lt;int&gt; greater;
      for (auto i = 1; i &lt; nums.size(); ++i) {
          int num = nums.at(i);
          if (num &lt; 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;
  }
  </code></pre>
  
  <p>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？</p>
  
  <p>Sorry for any grammatical mistakes, English is not my native language.</p>