title: Mergesort implementation is slow
body: <p>I'am doing a report about different sorting algorithms in C++. What baffles me is that my <code>mergesort</code> seems to be slower than <code>heapsort</code> in both of the languages. What I've seen is that <code>heapsort</code> is supposed to be slower.</p>
  
  <p>My <code>mergesort</code> sorts an unsorted array with size <code>100000</code> at a speed of 19.8 ms meanwhile <code>heapsort</code> sorts it at 9.7 ms. The code for my <code>mergesort</code> function in C++ is as follows:</p>
  
  <pre><code>void merge(int *array, int low, int mid, int high) {
      int i, j, k;
      int lowLength = mid - low + 1;
      int highLength = high - mid;
  
      int *lowArray = new int[lowLength];
      int *highArray = new int[highLength];
  
      for (i = 0; i &lt; lowLength; i++)
          lowArray[i] = array[low + i];
      for (j = 0; j &lt; highLength; j++)
          highArray[j] = array[mid + 1 + j];
  
      i = 0; 
      j = 0; 
      k = low; 
      while (i &lt; lowLength &amp;&amp; j &lt; highLength) {
          if (lowArray[i] &lt;= highArray[j]) {
              array[k] = lowArray[i];
              i++;
          } else {
              array[k] = highArray[j];
              j++;
          }
          k++;
      }
  
      while (i &lt; lowLength) {
          array[k] = lowArray[i];
          i++;
          k++;
      }
  
      while (j &lt; highLength) {
          array[k] = highArray[j];
          j++;
          k++;
      }
  }
  
  void mergeSort(int *array, int low, int high) {
      if (low &lt; high) {
          int mid = low + (high - low) / 2;
  
          mergeSort(array, low, mid);
          mergeSort(array, mid + 1, high);
  
          merge(array, low, mid, high);
      }
  }
  </code></pre>