Method medianOfMedians

src/main/java/com/thealgorithms/others/BFPRT.java:94–102

Finds the median of medians as the pivot element. @param arr the input array @param begin the starting index @param end the ending index @return the median of medians

(int[] arr, int begin, int end)

     * @return the median of medians
     */
    public static int medianOfMedians(int[] arr, int begin, int end) {
        int num = end - begin + 1;
        int offset = num % 5 == 0 ? 0 : 1;
        int[] mArr = new int[num / 5 + offset];
        for (int i = 0; i < mArr.length; i++) {
            mArr[i] = getMedian(arr, begin + i * 5, Math.min(end, begin + i * 5 + 4));
        }
        return bfprt(mArr, 0, mArr.length - 1, mArr.length / 2);
    }

    /**
     * Partitions the array around a pivot.