java - QuickSort stack overflow for sorted arrays (works for other data sets) -

so tried best optimize quicksort algorithm run efficiently possible, sorted or sorted arrays, using pivot median of 3 values, , using insertion sort small partition sizes. have tested code large arrays of random values , works, when pass sorted array stack overflow error(ironic because led me find website). believe problem recursive calls(i know partitioning works other data sets @ least), can't quite see change.

this part of first semester data structures class code review well. thanks.

public void quicksort(arraylist<string> data, int firstindex, int numbertosort) {     if (firstindex < (firstindex + numbertosort - 1))         if (numbertosort < 16) {             insertionsort(data, firstindex, numbertosort);         } else {             int pivot = partition(data, firstindex, numbertosort);             int leftsegmentsize = pivot - firstindex;             int rightsegmentsize = numbertosort - leftsegmentsize - 1;             quicksort(data, firstindex, leftsegmentsize);             quicksort(data, pivot + 1, rightsegmentsize);         } }    public int partition(arraylist<string> data, int firstindex, int numbertopartition) {     int toobigndx = firstindex + 1;     int toosmallndx = firstindex + numbertopartition - 1;      string string1 = data.get(firstindex);     string string2 = data.get((firstindex + (numbertopartition - 1)) / 2);     string string3 = data.get(firstindex + numbertopartition - 1);     arraylist<string> randomstrings = new arraylist<string>();     randomstrings.add(string1);     randomstrings.add(string2);     randomstrings.add(string3);     collections.sort(randomstrings);     string pivot = randomstrings.get(1);     if (pivot == string2) {         collections.swap(data, firstindex, (firstindex + (numbertopartition - 1)) / 2);     }     if (pivot == string3) {         collections.swap(data, firstindex, firstindex + numbertopartition - 1);     }     while (toobigndx < toosmallndx) {         while ((toobigndx < toosmallndx) && (data.get(toobigndx).compareto(pivot) <= 0)) {             toobigndx++;         }         while ((toosmallndx > firstindex) && (data.get(toosmallndx).compareto(pivot) > 0)) {             toosmallndx--;         }         if (toobigndx < toosmallndx) {// swap             collections.swap(data, toosmallndx, toobigndx);         }     }     if (pivot.compareto(data.get(toosmallndx)) >= 0) {         collections.swap(data, firstindex, toosmallndx);         return toosmallndx;     } else {         return firstindex;     } } 

in partition method use element outside range:

string string1 = data.get(firstindex); string string2 = data.get((firstindex + (numbertopartition - 1)) / 2); string string3 = data.get(firstindex + numbertopartition - 1); 

(firstindex + (numbertopartition - 1)) / 2 not index of middle element. (firstindex + (firstindex + (numbertopartition - 1))) / 2

= firstindex + ((numbertopartition - 1) / 2).

in fact if firstindex > n/2 (where n number of elements in input) you're using element index smaller firstindex. sorted arrays means choose element @ firstindex pivot element. therefore recursion depth in

,

which causes stack overflow large enough inputs.