Not understanding median of medians algorithm to find k-th element

Question

Below is my code for trying to understand the median of medians algorithm (using blocks of size 5). I understand how to get medians of the input, but I'm not sure how to code the block to keep recursing the input until I just have the median. Then after getting that median, I'm not sure how to use it as a pivot to throw away the useless information to partition the input. getMediansArray returns an array of size ceil(input.length/5) and getMedians just returns the median from an array (only used on arrays of length <= 5).

public static int[] findKthElement(int[] input, int k) {
    int numOfMedians = (int) Math.ceil(input.length/5.0);
    int[] medians = new int[numOfMedians];
    medians = getMediansArray(input, medians)

    // (1) This only gets the first iteration of medians of the
    // input. How do I recurse on this until I just have one median?

    // (2) how should I partition about the pivot once I get it?
}

public static int[] getMediansArray(int[] input, int[] medians) {
    int numOfMedians = (int) Math.ceil(input.length/5.0);
    int[] five = new int[5];

    for (int i = 0; i < numOfMedians; i++) {
        if (i != numOfMedians - 1) {
            for (int j = 0; j < 5; j++) {
                five[j] = input[(i*5)+j];
            }
            medians[i] = getMedian(five);
        } else {
            int numOfRemainders = input.length % 5;
            int[] remainder = new int[numOfRemainders];
            for (int j = 0; j < numOfRemainders; j++) {
                remainder[j] = input[(i*5)+j];
            }
            medians[i] = getMedian(five);
        }
    }
    return medians;
}

public static int getMedian(int[] input) {
    Arrays.sort(input);
    if (input.length % 2 == 0) {
        return (input[input.length/2] + input[input.length/2 - 1]) / 2;
    }
    return input[input.length/2];
}

Answer 1

Median of medians is basically just the quick-select algorithm (http://en.wikipedia.org/wiki/Quickselect) improved. While quick-select has O(n) average time complexity, it can slow down to O(n^2) for tricky input.

What you do after finding a median of medians is nothing but an iteration of quick-select algorithm. Median of medians has a nice property that it will be always larger than 30% of elements and smaller than 30% of elements. This guarantees that quick-select using median of medians for a pivot will run in worst time complexity of O(n). Refer to: http://en.wikipedia.org/wiki/Median_of_medians

I suggest you start by implementing quick-select. Once you do that, you can use code you already have to select pivot in each step of quick-select.