What exactly is special on this case that my median algorithm doesn't work anymore?

Question

I wrote a code in java for school to compute the median of an array. We have some test cases for this. The first column is the input, the second the expected and the third the actual output. Is anything special on the case that does not work? I've worked so long on this code now and slowly but surely i am getting frustrated. I really don't know where or why my code does not work in this specific scenario. the code is the following:

/**
 * This class calculates the median of a list to use it in quicksort for a runtime of O(log(n));
 * @author Niklas
 *
 */
public class Median {

    /**
     * The position i.
     */
    private static int positionI = -1;

    /**
     * a help array for the quicksort algorithm.
     */
    private static int[] quicksortArray;

    /**
     * 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.length == 0 || numbers == null) {
            throw new IllegalArgumentException("Array must contain values");
        }
        // avoiding that positionI is part of the recursion
        if (positionI == -1) {
            positionI = (int) Math.floor((double) ((numbers.length + 1) / 2));
        }

        // Step 1: dividing the list into groups.

        int[] medians = new int[(int) Math.ceil((float) numbers.length / 5)];
        int[] subArray = new int[5];
        int positionForMedianArray = 0;

        // the end case that the array is < 5.
        if (numbers.length <= 5) {
            sortArray(numbers);
            if (positionI <= numbers.length) {
                return numbers[positionI - 1];
            }
            return numbers.length % 2 == 0 ? numbers[(numbers.length / 2) - 1] : numbers[numbers.length / 2];
        }

        for (int i = 0; i < numbers.length; i += 5) {
            if (numbers.length < i + 5) {
                subArray = Arrays.copyOfRange(numbers, i, numbers.length);
            } else {
                subArray = Arrays.copyOfRange(numbers, i, i + 5);
            }
            // Step 2: calculate the median of each subArray.
            sortArray(subArray);
            medians[positionForMedianArray] = subArray.length % 2 == 0 ? subArray[subArray.length / 2 - 1]
                    : subArray[subArray.length / 2];
            positionForMedianArray += 1;

        }

        // Step 3: calculate x recursively
        int x = lowerMedian(medians);

        // Step 4: partioniate the lists.

        // computing how big the arrays have to be because arraylists doesnt work as
        // good in this code.
        int countS = 0;
        int countG = 0;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] < x) {
                countS += 1;
            } else if (numbers[i] > x) {
                countG += 1;
            }
        }

        // creating the arrays with the right size.
        int[] smaller = new int[countS];
        int[] greater = new int[countG];

        countS = 0;
        countG = 0;

        // filling the Arrays (L1 and L2).
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] < x) {
                smaller[countS] = numbers[i];
                countS += 1;
            } else if (numbers[i] > x) {
                greater[countG] = numbers[i];
                countG += 1;
            }
        }

        int k = smaller.length + 1;

        // for testing
//      System.out.println("\nnumbers: " + Arrays.toString(numbers));
//      System.out.println("position i: " + positionI);
//      System.out.println("SubArray " + (positionForMedianArray) + ": " + Arrays.toString(subArray));
//      System.out.println("Median Array im Durchlauf " + (positionForMedianArray) + ": " + Arrays.toString(medians));
//      System.out.println("x: " + x);
//      System.out.println("L1: " + Arrays.toString(smaller));
//      System.out.println("L2: " + Arrays.toString(greater));
//      System.out.println("Position k: " + k);

        if (positionI < k) {
            return lowerMedian(smaller);
        } else if (positionI > k) {
            positionI -= k;
            return lowerMedian(greater);
        }
        return x;

    }
    /**
     * Sorts the given array in an inefficent way.
     * 
     * @param numbers the array to sort.
     */
    private static void sortArray(int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            for (int j = 0; j < numbers.length; j++) {
                if (numbers[i] < numbers[j]) {
                    int tempVar = numbers[j];
                    numbers[j] = numbers[i];
                    numbers[i] = tempVar;

                }

            }
        }
    }

I would appreciate any kind of help!

Answer 1

I'm not sure why your approach for calculating low median is so complicated. All you need to do is sort the list of number and if the list has odd number of values then just return value at <array length> / 2 and if the list has even number of values then return value at (<array_length> / 2) - 1. Regarding the sorting the input list, you can either implement your own quicksort algorithm or use Arrays.sort. Below is a potential approach to calculate lower median using Java built-in sort method.

    public static int lowerMedian(int[] numbers) {
        Arrays.sort(numbers, 0, numbers.length);
        int length = numbers.length;
        if (length == 0) {
            return 0;
        } else if (length % 2 == 0) {
            return numbers[(length / 2) - 1];
        } else {
            return numbers[length / 2];
        }
    }