static int quickSelectAdaptive()

in commons-numbers-arrays/src/main/java/org/apache/commons/numbers/arrays/QuickSelect.java [587:671]
61 lines of code
16 McCabe index (conditional complexity)

    static int quickSelectAdaptive(double[] a, int left, int right, int ka, int kb,
            int[] bounds, int flags) {
        int l = left;
        int r = right;
        int m = flags;
        while (true) {
            // Select when ka and kb are close to the same end
            // |l|-----|ka|kkkkkkkk|kb|------|r|
            if (Math.min(kb - l, r - ka) < LINEAR_SORTSELECT_SIZE) {
                sortSelect(a, l, r, ka, kb);
                bounds[0] = kb;
                return ka;
            }

            // Only target ka; kb is assumed to be close
            int p0;
            final int n = r - l;
            // f in [0, 1]
            final double f = (double) (ka - l) / n;
            // Record the larger margin (start at 1/4) to create the estimated size.
            // step        L     R
            // far left    1/12  1/3   (use 1/4 + 1/32 + 1/64 ~ 0.328)
            // left        1/6   1/4
            // middle      2/9   2/9   (use 1/4 - 1/32 ~ 0.219)
            int margin = n >> 2;
            if (m < MODE_SAMPLING && r - l > FR_SAMPLING_SIZE) {
                // Floyd-Rivest sample step uses the same margins
                p0 = sampleStep(a, l, r, ka, bounds);
                if (f <= STEP_FAR_LEFT || f >= STEP_FAR_RIGHT) {
                    margin += (n >> 5) + (n >> 6);
                } else if (f > STEP_LEFT && f < STEP_RIGHT) {
                    margin -= n >> 5;
                }
            } else if (f <= STEP_LEFT) {
                if (f <= STEP_FAR_LEFT) {
                    margin += (n >> 5) + (n >> 6);
                    p0 = repeatedStepFarLeft(a, l, r, ka, bounds, m);
                } else {
                    p0 = repeatedStepLeft(a, l, r, ka, bounds, m);
                }
            } else if (f >= STEP_RIGHT) {
                if (f >= STEP_FAR_RIGHT) {
                    margin += (n >> 5) + (n >> 6);
                    p0 = repeatedStepFarRight(a, l, r, ka, bounds, m);
                } else {
                    p0 = repeatedStepRight(a, l, r, ka, bounds, m);
                }
            } else {
                margin -= n >> 5;
                p0 = repeatedStep(a, l, r, ka, bounds, m);
            }

            // Note: Here we expect [ka, kb] to be small and splitting is unlikely.
            //                   p0 p1
            // |l|--|ka|kkkk|kb|--|P|-------------------|r|
            // |l|----------------|P|--|ka|kkk|kb|------|r|
            // |l|-----------|ka|k|P|k|kb|--------------|r|
            final int p1 = bounds[0];
            if (kb < p0) {
                // Entirely on left side
                r = p0 - 1;
            } else if (ka > p1) {
                // Entirely on right side
                l = p1 + 1;
            } else {
                // Pivot splits [ka, kb]. Expect ends to be close to the pivot and finish.
                // Here we set the bounds for use after median-of-medians pivot selection.
                // In the event there are many equal values this allows collecting those
                // known to be equal together when moving around the medians sample.
                if (kb > p1) {
                    sortSelectLeft(a, p1 + 1, r, kb);
                    bounds[0] = kb;
                }
                if (ka < p0) {
                    sortSelectRight(a, l, p0 - 1, ka);
                    p0 = ka;
                }
                return p0;
            }
            // Update mode based on target partition size
            if (r - l > n - margin) {
                m++;
            }
        }
    }