title: why does shell sort outperform heap sort with large arrays?
body: <p>This is part of an assignments in which we have to compare different sorting algorithms. In order to get an unbiased testing processed I applied some basic concepts of statistics. Instead of running a single test I executed a sample of tests with different array sizes. The sample size is constant, 100, and the number of elements per round varied: one thousand, ten thousand, one-hundred thousand, one million and ten million elements respectively and the arrays were randomly filled.</p>
  
  <p>Due to the restrictions of insertion sort, it wasn’t tested after one-hundred thousand elements. The number of comparisons and array accesses that every algorithm performed were recorded as well.</p>
  
  <p>At the end of the report shell sort outperforms heap sort. The reasons are not clear to me. Might it have to do with the way the arrays were filled (with random numbers)?</p>
  
  <p><a href="https://i.stack.imgur.com/49kbP.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/49kbP.jpg" alt="average running time with an array of 10 million elements"></a></p>
  
  <p>This is the code used for both algorithms:</p>
  
  <pre><code>// source: Data Structures and Problem Solving Using C++ 2nd Edition
  // page 329
  void sortingAlgs::shellSort(std::vector&lt;int&gt;&amp; array, int n) {
      for (int gap{static_cast&lt;int&gt;(n/2)}; gap &gt; 0;
           gap = gap == 2 ? 1 : static_cast&lt;int&gt;(gap / 2.2)) { // floor
          for (int i{gap}; i &lt; n; i++) {
              int temp = array[i];
              int j = i;
  
              for (; j &gt;= gap &amp;&amp; temp &lt; array[j-gap]; j -= gap) {
                  array[j] = array[j-gap];
              }
              array[j] = temp;
          }
  }
  }
  
  
  // source: http://quiz.geeksforgeeks.org/heap-sort/
  // source: Introduction to Algorithms page 154
      void sortingAlgs::max_heapify(std::vector&lt;int&gt;&amp; array, int n, int i) {
      int largest = i;      // Initialize largest as root
      int l = 2*i + 1;  // left = 2*i + 1
      int r = 2*i + 2;  // right = 2*i + 2
  
      // If left child is larger than root
      if (l &lt; n &amp;&amp; array[l] &gt; array[largest])
          largest = l;
  
      // If right child is larger than largest so far
      if (r &lt; n &amp;&amp; array[r] &gt; array[largest])
          largest = r;
  
      // If largest is not root
      if (largest != i) {
          std::swap(array[i], array[largest]);
          // Recursively heapify the affected sub-tree
          max_heapify(array, n, largest);
      }
  }
  
  // source: http://quiz.geeksforgeeks.org/heap-sort/
  // source: Introduction to Algorithms page 160
  void sortingAlgs::heapSort(std::vector&lt;int&gt;&amp; array, int n) {
      // Build heap (re-arrange array)
      for (int i = (n / 2) - 1; i &gt;= 0; i--) {
          max_heapify(array, n, i);
      }
  
      // One by one extract an element from heap
      for (int i = n-1; i &gt;= 0; i--)
      {
          // Move current root to end
          std::swap(array[0], array[i]);
          // call max heapify on the reduced heap
          max_heapify(array, i, 0);
      }
  }
  </code></pre>