sorting - Nonworking QuickSort with InsertionSort implemention in Java? -

i have tried write quicksort method implements insertion sort speed smaller arrays.

my methods insertionsort , quicksort beautifully sorts arrays, when start mixing them lists numbers place switched when comparing sorted list.

first quicksort:

public class qsort implements intsorter { public enum order {     random, first, last, mypivot } private final order order; private random random;  public qsort(order order) {     this.order = order;     random = new random(); }   public int[] sort(int[] v) {     return qsort(v, 0, v.length - 1); }  // sorts elements of subvector v[first..last]. protected int[] qsort(int[] v, int first, int last) {     if(first >= last) // less 2 elements         return v;      int p = 0;     // choose pivot element.     if(order == order.first)         p = v[first];     else if(order == order.last)         p = v[last];     else if(order == order.mypivot) {          //the median of first, middle , last element          //chosen median         if((v[first] >= v[(last - first)/2 +first] && v[first] <= v[last])          || (v[first] <= v[(last - first)/2 +first] && v[first] >= v[last])) {             p = v[first];         }         else if((v[last] >= v[(last - first)/2 +first] && v[last] <= v[first])          || (v[last] <= v[(last - first)/2 +first] && v[last] >= v[first])) {             p = v[last];         }         else if((v[(last - first)/2 +first] >= v[last] && v[(last - first)/2 +first] <= v[first])          || (v[(last - first)/2 +first] <= v[last] && v[(last - first)/2 + first]>= v[first])) {              p = v[last/2];         }     }     else if(order == order.random) {         int r = random.nextint(last - first) + first;         p = v[r];     }       int[] lowhigh = partition(v, first, last, p);      qsort(v, first, lowhigh[0]-1);     qsort(v, lowhigh[1]+1, last);     return v; }  /**  * reorders elements of subarray v[first..last]  * elements in v[first..low-1] less pivot,  * elements in v[low..high] equal pivot,  * elements in v[high+1..last] greater pivot.  *   * precondition: first < last.  */ protected int[] partition(int[] v, int first, int last, int pivot) {     int low = first;     int mid = first;     int high = last;      while (mid <= high) {          int = v[mid];          if (a < pivot) {             v[mid] = v[low];             v[low] = a;             low++;             mid++;         }          else if (a == pivot) {             mid++;         }          else { // > pivot             v[mid] = v[high];             v[high] = a;             high--;         }     }     int[]returnarray = new int[2];     returnarray[0] = low;     returnarray[1] = high;      return returnarray; } 

note both implements insorter, interface make easier test them later. contains sort method.

and next method mixes quicksort insertionsort, named mixsort:

public class mixsort extends qsort {  private insertionsort isort; //enum inheritet qsort allows orders random, first, last private order order; //arraysize when change insertionsort private int k; private random random;  public mixsort(int k, order order) {     isort = new insertionsort();     this.order = order;     this.k = k;     random = new random(); }  /**  * sorts array in ascending order through quicksort implementing insertionsort  * @param v     array sorted  * @param first beginning of array  * @param   last last index of array  * @return sorted array  */ @override public int[] qsort(int[] v, int first, int last) {     if (first >= last - 1) // less 2 elements         return v;      int p = 0;     // choose pivot element.     if(order == order.first)         p = v[first];     else if(order == order.last)         p = v[last];     else if(order == order.mypivot)     {         //the median of first, middle , last element          //chosen median         if((v[first] >= v[(last - first)/2 +first] && v[first] <= v[last])          || (v[first] <= v[(last - first)/2 + first] && v[first] >= v[last]))         {             p = v[first];         }         else if((v[last] >= v[(last - first)/2 +first] && v[last] <= v[first])          || (v[last] <= v[(last - first)/2 + first] && v[last] >= v[first]))         {             p = v[last];         }         else if((v[(last - first)/2 + first] >= v[last] && v[(last - first)/2 + first]<= v[first])          || (v[(last - first)/2 + first] <= v[last] && v[(last - first)/2 +first] >= v[first]))         {             p = v[last/2];         }     }     else if(order == order.random)     {        int r = random.nextint(last - first) + first;        p = v[r];     }        if(last - first <= k)     {         this.isort(v, first, last);     }     else     {         // partition elements every number of         // v[first..mid] <= p , every number of v[mid+1..last] > p.         int[] lowhigh = partition(v, first, last, p);         this.qsort(v, first, lowhigh[0]-1);         this.qsort(v, lowhigh[1]+1, last);     }       return v; }  /**  * method utilizes insertion sort sort given array of ints.   *   * @param         array sorted  * @param first     starting index of array  * @param last      last index sorted in array  * @return          sorted array produced sort()   */ public int[] isort(int[] a, int first, int last) {     if(a.length <= 1) //array contains less 2 elements         return a;      int save = 0;    (int = first + 1; < last; i++)    {      save = a[i];      int j = 0;      (j = -1; j >= first && save < a[j]; j--)       {         a[j + 1] = a[j];      }      a[j + 1] = save;   }     return a; } 

note mixsort extends quicksort.

i can not figure out why own mixsort doesn't work, though faults have seen in sorted lists hints @ problems pivotpoint. though since code shared quicksort, such problems should not arise since quicksort runs without failure.

an example of piece of array looks after sorting following:

• 19 19
• 21 21
• 22 23
• 23 24
• 24 24
• 24 25
• 25 22
• 30 30

the array correctly sorted on left , same array sorted mixsort on right. i'm not sure how represent array though, list have do. note number 22 have been inserted later in list.

thanks beforehand.

as supposed did not read code, seeing like

v[first] >= v[last/2] 

in pivot selection looks extremely fishy in eyes. last supposed end of range , want @ elements v[first..last] in sort (shamelessly using pseudo-ruby @ point, guess idea). if given first=100 , last=150 @ element v[75] not belong elements want sort @ point.

not having checked code (and not having example , how goes wrong (hint, hint ...)) hard verify wether real problem, might give try.