I am getting an out of bounds exception thrown when I use this median of medians code to find a given location of k. I am not sure of the exact size at which it begins throwing the error, but the code works for arrays of size < 75, and the error starts when I exceed array size 100.
private static int mmQuickSortRecursive(Integer[] a, int k) {
if (a.length <= 10)
{
Arrays.sort(a);
return a[k-1];
}
int n = a.length;
// partition L into subsets S[i] of five elements each (n/5 subsets).
ArrayList<Integer[]> list = new ArrayList<Integer[]>();
int cnt = 0;
int m = n/5;
for( int i = 0; i < m; i++ ) {
Integer[] arr = new Integer[5];
for( int j = 0; j < 5; j++ ) {
if( cnt == n )
break;
arr[j] = a[cnt++];
}
Arrays.sort(arr);
list.add(arr);
}
Integer[] x = new Integer[m];
for (int i = 0; i< m; i++ ) {
x[i] = list.get(i)[2];
}
int v = x[0];
if(x.length > 2) {
///////// ERROR THROWN ON BELOW LINE /////////////////
v = (x.length%2 == 0)? x[x.length%2-1]: x[x.length/2];
}
// partition L into 3 parts, L1<M, L2=M, L3>M
Integer[] l = partition_left( a, v );
Integer[] r = partition_right( a, v );
if( k == l.length+1 ) {
return v;
} else if( k <= l.length ){
return mmQuickSortRecursive(l,k);
} else {
return mmQuickSortRecursive(r,k-l.length-1);
}
}
