title: Why is Boost's QuickSort slower compared to Julia's QuickSort?
body: <p>I am comparing the performance between Julia and C++. Then I found quick sort is much faster in Julia (and even faster than C++), especially when the size of array is very big.</p>
  <p>Can anyone explain the reasons?</p>
  <p><strong>quickSort.jl</strong></p>
  <pre><code>include(&quot;../dimension.jl&quot;)
  function execute()  
      n = getDimension()
      print(stderr, &quot;Julia,quickSort_optim,$n,&quot;);  # use default delimiter
      arr = zeros(Int32, n)
      for i = 1:n
          arr[i] = (777*(i-1)) % 10000
      end
      if n &gt; 0
          sort!(arr; alg=QuickSort)
      end
  end
  
  # executing ...
  execute()
  </code></pre>
  <p><strong>quickSort_boost.cpp</strong></p>
  <pre><code>#include &quot;dimension.h&quot; 
  #include &lt;boost/lambda/lambda.hpp&gt;
  #include &lt;boost/sort/pdqsort/pdqsort.hpp&gt;
  #include &lt;iostream&gt;
  #include &lt;iterator&gt;
  #include &lt;algorithm&gt;
   
  using namespace std;
  using namespace boost::sort; 
  
  int main()
  {
      int n = getDimension();
      cerr &lt;&lt; &quot;C++,quickSort_boost,&quot; &lt;&lt; n &lt;&lt; &quot;,&quot;;
      
      vector&lt;int&gt; arr(n);
      unsigned long long w;
      for(int i = 0; i &lt; n; ++i){  // array for sorting
          w = (777*i) % 10000; // Array with values between 0 and 10000
          arr[i] = w;
      }
      
      if (n &gt; 0){
          pdqsort_branchless(arr.begin(), arr.end(), [](const int &amp;a, const int &amp;b){return ( a &lt; b );});
      }
      
      return 0;
  }
  </code></pre>
  <p><strong>Comparison</strong></p>
  <p><a href="https://i.stack.imgur.com/Qf32r.png" rel="noreferrer"><img src="https://i.stack.imgur.com/Qf32r.png" alt="Performance chart plotting size of array vs runtime" /></a></p>
  <p><strong>Note</strong></p>
  <p>The function getDimension() is used to get the array size.</p>
  <p>The execution time is measured with the shell command: /usr/bin/time under Ubuntu. Compiler: clang version 6.0.0-1ubuntu2. Optimization level: -02. CPU: Intel i7-3820QM</p>
  <p>The reason that I compared the whole execution time rather than just the algorithm itself is because I want to compare the performance between these two languages, which simulates a real application scenario.</p>
  <p>In Julia official document, it writes: QuickSort: good performance for large collections.
  Is this because Julia uses a special implementation inside the algorithm.</p>
  <p><strong>More samples</strong></p>
  <p>I run the test with more samples. It seems that <strong>the distribution of the data is the issue.</strong></p>
  <ol>
  <li>best case with broadly distributed data:</li>
  </ol>
  <pre><code>function execute()  # julia code segment for specifying data
      for i = 1:n
          arr[i] = i
      end
  
  for(int i = 0; i &lt; n; ++i){  // c++ boost code segment for specifying data
      arr[i] =  i + 1; 
  }
  </code></pre>
  <p><a href="https://i.stack.imgur.com/SiDph.png" rel="noreferrer"><img src="https://i.stack.imgur.com/SiDph.png" alt="QuickSort-best case with broadly distruted data" /></a></p>
  <ol start="2">
  <li>worst case with broadly distributed data:</li>
  </ol>
  <pre><code>function execute()  # julia code segment for specifying data
      for i = 1:n
          arr[i] = n - i + 1
      end
  
  for(int i = 0; i &lt; n; ++i){  // c++ boost code segment for specifying data
      arr[i] =  n - i;  
  }
  </code></pre>
  <p><a href="https://i.stack.imgur.com/Cw8s3.png" rel="noreferrer"><img src="https://i.stack.imgur.com/Cw8s3.png" alt="QuickSort-worst case with broadly distruted data" /></a></p>
  <ol start="3">
  <li>Concentrated distributed data</li>
  </ol>
  <pre><code>function execute()  # julia code segment for specifying data
      for i = 1:n
          arr[i] = i % 10
      end
  
  for(int i = 0; i &lt; n; ++i){  // c++ boost code segment for specifying data
      arr[i] =  (i + 1) % 10;  
  }
  </code></pre>
  <p><a href="https://i.stack.imgur.com/lmZEH.png" rel="noreferrer"><img src="https://i.stack.imgur.com/lmZEH.png" alt="Concentrated distributed data" /></a></p>
  <p><a href="https://github.com/David1231123/quickSort-bechmark-in-Julia-and-C-" rel="noreferrer">My source code</a></p>