title: Looking for error in C++ Quicksort / Insertion sort combo
body: <p>Im trying to build a the quicksort / insertion sort combo, as some say its fairly fast, as it tackles the larger subarrays with quicksort and the smaller arrays with insertion sort, but something is definitely not correct.  I've been testing the sorting with some files I generated.  I'm currently using a file of 1,000,000 numbers, with the range limit on each number being from 1 to 1,000,000.  Prior to adding the insertion sort, I was able to sort the 1 million numbers in about 0.2 seconds, after adding insertion sort as a conditional if statement, I'm lucky to sort 100,000 numbers in less than 4 seconds, so I know there's an error in the code, but I can't find it.  My code is just an amalgam of different online references for these types of sorting methods, I don't claim the code as my own and can provide links to the original if necessary.  However, the references I used weren't written in C++ and were class-oriented, so I had to make changes, which is why I think there's an error.</p>
  
  <pre><code>void modifiedQuickSort(arrPtr &amp;arrayPointer, int first, int last)
  {
      int firstTemp = first, lastTemp = last;
      int temp;
      int pivot = arrayPointer[(first + last) / 2];
  
  
      if((last - first) &lt; 10)
      {
          insertionSort(arrayPointer, last + 1);
      }
  
      else
      {
          // Partitioning Step
          while (firstTemp &lt;= lastTemp)
          {
              while (arrayPointer[firstTemp] &lt; pivot)
                  firstTemp++;
  
              while (arrayPointer[lastTemp] &gt; pivot)
                  lastTemp--;
  
              if (firstTemp &lt;= lastTemp)
              {
                  temp = arrayPointer[firstTemp];
                  arrayPointer[firstTemp] = arrayPointer[lastTemp];
                  arrayPointer[lastTemp]  = temp;
                  firstTemp++;
                  lastTemp--;
              }
          }
  
          // Recursive step
          if (first &lt; lastTemp)
              modifiedQuickSort(arrayPointer, first, lastTemp);
  
          if (firstTemp &lt; last)
              modifiedQuickSort(arrayPointer, firstTemp, last);
      }
  }
  
  void insertionSort(arrPtr &amp;arrayPointer, const int &amp;arraySize)
  {
      int i, key, j;
  
      for (i = 1; i &lt; arraySize; i++)
      {
          key = arrayPointer[i];
  
          j = i-1;
  
          /* Move elements of arr[0..i-1], that are
           greater than key, to one position ahead
           of their current position */
          while (j &gt;= 0 &amp;&amp; arrayPointer[j] &gt; key)
          {
              arrayPointer[j+1] = arrayPointer[j];
              j = j-1;
          }
          arrayPointer[j+1] = key;
      }
  }
  </code></pre>