title: Quicksort with insertion sort in java
body: <p>Hello I have been trying to implement my quicksort algorithm with insertion sort according to how our teacher told us, but I just can't figure out exactly what to do...And my teacher's pseudo code seems doesn't seem to help me much... Anyways, I have searched online but I can't find anything.
  Here is the pseudo code he gaves us</p>
  
  <pre><code>voidTQuickSort(int[]A, low,high)
  while low &lt; high do
  p = DPartition(A,low,high)
  TQuicksort(A,low,high)
  low = p + 1
  end while
  </code></pre>
  
  <p>He also said "In quicksort switch to insertionSort for recursive calls on small subarrays, after partitioning, first recurse smaller subarray and then make a tail call to larger subarray"</p>
  
  <p>First, I'd like to know, what is a tail call, and which array is he talking about? In my original quicksort I have this</p>
  
  <pre><code>public void quicksort(int numbers[], int start, int end)   
      {   
          //Condition to continue recursion
          if(start &lt; end)
          {
              //Set up my index as the start or end point for recursion
              int myIndex = partition(numbers, start, end);
  
              //Recursive algorithm for left and right side of the array
              quicksort(numbers, start, myIndex-1);
              quicksort(numbers, myIndex + 1, end);
          }
      }
  </code></pre>
  
  <p>And in my attempt, I get a stack overflow, however, if I place those two sub arrays back into while loop, my runtime goes from 1 ms on quicksort, to 24 ms for the so called "improved" quicksort</p>
  
  <p>Here's the attempt</p>
  
  <pre><code>public void quicksortImproved(int numbers[], int start, int end)   
      {   
  
          //Condition to continue recursion
          while(start &lt; end)
          {
              //Set up my index as the start or end point for recursion
              int myIndex = partition(numbers, start, end);
  
              //Recursive algorithm
              quicksortImproved(numbers, start, end);
              start = myIndex + 1;
          }
          insertionSortTwo(numbers);
  
  
      }
  </code></pre>
  
  <p>Any help is appreciated! Thank you</p>
  
  <p>Function partition and insertionsortTwo </p>
  
  <pre><code>public int partition(int[] numbers, int start, int end)
      {
          //Declaring my pivot, start and end indexes
          int pivot = numbers[end];
          int small = start;
          int big = end - 1;
  
          //Begin loop while index of small is less than index of big
          while(small &lt;= big)
          {
              //If the element @ numbers[small] is smaller than element at pivot
              //Then increment small index by 1
              while (small &lt;= big &amp;&amp; numbers[small] &lt;= pivot)
              {
                  small++;
              }
              //If the element @ numbers[big] is bigger than element at pivot
              //Then decrement index by 1
              while(big &gt;= small &amp;&amp; numbers[big] &gt;= pivot)
              {
                  big--;
              }
              //If small index is smaller than big index
              //Swap elements @ number[small] with element @ number[big]
              if(small &lt; big)
              {
                  numbers[small] = returnFirst(numbers[big], numbers[big] = numbers[small]);
              }
          }
          //Swap pivot with the presumed middle element and return small index
          numbers[end] = returnFirst(numbers[small], numbers[small] = numbers[end]);
          return small;
      }
  
  
      public void insertionSortTwo(int[] numbers)
      {
          //Loop from index 1 to end, element @ numbers[0] is in the sorted array
          for (int i = 1; i &lt; numbers.length; i++)
          {
              //Setting up second array index variable
              //Loop to create new array in sorted order
              for(int j = i; j &gt; 0 &amp;&amp; numbers[j] &lt; numbers[j - 1]; j--)
              {
                  //If element @ number[j] is smaller than element @ number[j - 1]
                  //swap element @ numbers[j] with element @ numbers[j - 1] and decrement j
                  numbers[j] = returnFirst(numbers[j - 1], numbers[j - 1] = numbers[j]);
              }
          }
      }
  </code></pre>