java - QuickSort breaking -

i trying parallelize quick sort wrote serial version first partition , recursive sort on both partitions. works.. until sizes of > 100,000 in case if 1 of partitions big goes forever , never finishes. can't figure out why is. run in 13-15 ms @ 100k @ 120k either run @ around same time or not @ all.

for partition picked pivot based on median of first, middle, , last elements of current partition , if equal goes last element.

here's partition:

private static int partition(int low, int high, int[] array){     //get median of first, last, , middle element in our section     int lval, hval, mval, pindex, pval;     lval = array[low];     hval = array[high];     mval = array[((high-low+1)/2) + low];     //system.out.println("low: " + low + "high: " + high);     if (lval < hval && lval > mval || lval > hval && lval < mval){         pindex = low;         //system.out.println("picking low index: " + low);     } else if (hval < lval && hval > mval || hval > lval && hval < mval){         pindex = high;         //system.out.println("picking high index: " + high);     } else if (mval < hval && mval > lval || mval > hval && mval < lval){         pindex = (high-low+1)/2+low;         //system.out.println("picking middle index: " + ((high-low+1)/2)+low);     } else {         pindex = high;     }     pval = array[pindex];      //put pivot @ of our chunk     int temp = array[pindex];     array[pindex] = array[high];     array[high] = temp;     //printarray();      //two pointer method.. high , low.. move them , swap if low > pivot , high < pivot     int left = low;     int right = high - 1;     pindex = 0;      while (left <= right){         while(left <= high && array[left] < pval){             left++;         }         while(right >= low && array[right] > pval){             right--;         }         //if both elements @ pointers on wrong side swap         if(left < right){             temp = array[left];             array[left] = array[right];             array[right] = temp;             left++;             right--;             //printarray();         }     }     //need pivot high low pointer ended     temp = array[left];     array[left] = array[high];     array[high] = temp;      //printarray();     return left; } 

this doesn't seem take long no matter how many elements there i'm not sure if cause or not.

here sort:

public static void sort (int low, int high, comparator c, int[] array){         if(high - low > 1) {             int pindex = partition(low, high, array);              sort(low, pindex - 1, c, array);             sort(pindex + 1, high, c, array);         }  } 

any ideas on why freezing @ point fantastic. ran type of partition found on internet , ran fine @ size gave want know wrong this. here unit test i'm using test it.

@test public void testsortstandard() throws exception {     int size = 100000;     //test randoms 10000     int[] = new int[size];     random r = new random();     for(int = 0; < size; i++){         a[i] = r.nextint();     }     quicksort.sort(0, a.length-1, null, a);      testissorted(a); } 

it continues run , run , run. have feeling partitioning things on , on , on again wastefully.