# How to implement the medians of medians algorithm in Java

I am trying to implement the median of medians algorithm in Java. The algorithm shall determine the median of a set of numbers. I tried to implement the pseudo code on wikipedia:

https://en.wikipedia.org/wiki/Median_of_medians

I am getting a buffer overflow and don’t know why. Due to the recursions it’s quite difficult to keep track of the code for me.

```    import java.util.Arrays;

public class MedianSelector {
private static final int CHUNK = 5;

public static void main(String[] args) {
int[] test = {9,8,7,6,5,4,3,2,1,0,13,11,10};
lowerMedian(test);
System.out.print(Arrays.toString(test));
}

/**
* Computes and retrieves the lower median of the given array of
* numbers using the Median algorithm presented in the lecture.
*
* @param input numbers.
* @return the lower median.
* @throw IllegalArgumentException if the array is {@code null} or empty.
*/
public static int lowerMedian(int[] numbers) {
if(numbers == null || numbers.length == 0) {
throw new IllegalArgumentException();
}

return numbers[select(numbers, 0, numbers.length - 1, (numbers.length - 1) / 2)];
}

private static int select(int[] numbers, int left, int right, int i) {

if(left == right) {
return left;
}

int pivotIndex = pivot(numbers, left, right);
pivotIndex = partition(numbers, left, right, pivotIndex, i);

if(i == pivotIndex) {
return i;
}else if(i < pivotIndex) {
return select(numbers, left, pivotIndex - 1, i);
}else {
return select(numbers, left, pivotIndex + 1, i);
}
}

private static int pivot(int numbers[], int left, int right) {
if(right - left < CHUNK) {
return partition5(numbers, left, right);
}

for(int i=left; i<=right; i=i+CHUNK) {
int subRight = i + (CHUNK-1);

if(subRight > right) {
subRight = right;
}

int medChunk = partition5(numbers, i, subRight);

int tmp = numbers[medChunk];
numbers[medChunk] = numbers[(int) (left + Math.floor((double) (i-left)/CHUNK))];
numbers[(int) (left + Math.floor((double) (i-left)/CHUNK))] = tmp;
}

int mid = (right - left) / 10 + left +1;
return select(numbers, left, (int) (left + Math.floor((right - left) / CHUNK)), mid);
}

private static int partition(int[] numbers, int left, int right, int idx, int k) {
int pivotVal = numbers[idx];
int storeIndex = left;
int storeIndexEq = 0;
int tmp = 0;

tmp = numbers[idx];
numbers[idx] = numbers[right];
numbers[right] = tmp;

for(int i=left; i<right; i++) {
if(numbers[i] < pivotVal) {
tmp = numbers[i];
numbers[i] = numbers[storeIndex];
numbers[storeIndex] = tmp;
storeIndex++;
}
}

storeIndexEq = storeIndex;

for(int i=storeIndex; i<right; i++) {
if(numbers[i] == pivotVal) {
tmp = numbers[i];
numbers[i] = numbers[storeIndexEq];
numbers[storeIndexEq] = tmp;
storeIndexEq++;
}
}

tmp = numbers[right];
numbers[right] = numbers[storeIndexEq];
numbers[storeIndexEq] = tmp;

if(k < storeIndex) {
return storeIndex;
}

if(k <= storeIndexEq) {
return k;
}

return storeIndexEq;
}

//Insertion sort
private static int partition5(int[] numbers, int left, int right) {
int i = left + 1;
int j = 0;

while(i<=right) {
j= i;
while(j>left && numbers[j-1] > numbers[j]) {
int tmp = numbers[j-1];
numbers[j-1] = numbers[j];
numbers[j] = tmp;
j=j-1;
}
i++;
}

return left + (right - left) / 2;
}
}
```

Confirm n (in the pseudo code) or i (in my code) stand for the position of the median? So lets assume our array is number = {9,8,7,6,5,4,3,2,1,0}. I would call select{numbers, 0, 9,4), correct?

I don’t understand the calculation of mid in pivot? Why is there a division by 10? Maybe there is a mistake in the pseudo code?

EDIT: It turns out the switch from iteration to recursion was a red herring. The actual issue, identified by the OP, was in the arguments to the 2nd recursive `select` call.

This line:

```return select(numbers, left, pivotIndex + 1, i);
```

should be

```return select(numbers, pivotIndex + 1, right, i);
```

I’ll leave the original answer below as I don’t want to appear to be clever than I actually was.

I think you may have misinterpreted the pseudocode for the `select` method – it uses iteration rather than recursion.

```private static int select(int[] numbers, int left, int right, int i) {

if(left == right) {
return left;
}

int pivotIndex = pivot(numbers, left, right);
pivotIndex = partition(numbers, left, right, pivotIndex, i);

if(i == pivotIndex) {
return i;
}else if(i < pivotIndex) {
return select(numbers, left, pivotIndex - 1, i);
}else {
return select(numbers, left, pivotIndex + 1, i);
}
}
```

And the pseudocode

```function select(list, left, right, n)
loop
if left = right then
return left
pivotIndex := pivot(list, left, right)
pivotIndex := partition(list, left, right, pivotIndex, n)
if n = pivotIndex then
return n
else if n < pivotIndex then
right := pivotIndex - 1
else
left := pivotIndex + 1
```

This would typically be implemented using a `while` loop:

```  private static int select(int[] numbers, int left, int right, int i) {
while(true)
{
if(left == right) {
return left;
}

int pivotIndex = pivot(numbers, left, right);
pivotIndex = partition(numbers, left, right, pivotIndex, i);

if(i == pivotIndex) {
return i;
}else if(i < pivotIndex) {
right = pivotIndex - 1;
}else {
left = pivotIndex + 1;
}
}
}
```

With this change your code appears to work, though obviously you’ll need to test to confirm.

```int[] test = {9,8,7,6,5,4,3,2,1,0,13,11,10};
System.out.println("Lower Median: " + lowerMedian(test));

int[] check = test.clone();
Arrays.sort(check);
System.out.println(Arrays.toString(check));
```

Output:

```Lower Median: 6
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13]
```