static void dualPivotQuickSelect()

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

    static void dualPivotQuickSelect(int[] a, int left, int right, UpdatingInterval k, int flags) {
        // If partitioning splits the interval then recursion is used for the left-most side(s)
        // and the right-most side remains within this function. If partitioning does
        // not split the interval then it remains within this function.
        int l = left;
        int r = right;
        int f = flags;
        int ka = k.left();
        int kb = k.right();
        final int[] upper = {0, 0, 0};
        while (true) {
            // Select when ka and kb are close to the same end,
            // or the entire range is small
            // |l|-----|ka|--------|kb|------|r|
            final int n = r - l;
            if (Math.min(kb - l, r - ka) < DP_SORTSELECT_SIZE ||
                n < (f & SORTSELECT_MASK)) {
                sortSelect(a, l, r, ka, kb);
                return;
            }
            if (kb - ka < DP_SORTSELECT_SIZE) {
                // Switch to single-pivot mode with Floyd-Rivest sub-sampling
                quickSelectAdaptive(a, l, r, ka, kb, upper, MODE_FR_SAMPLING);
                return;
            }
            if (f < 0) {
                // Excess recursion, switch to heap select
                heapSelect(a, l, r, ka, kb);
                return;
            }

            // Dual-pivot partitioning
            final int p0 = partition(a, l, r, upper);
            final int p1 = upper[0];

            // Recursion to max depth
            // Note: Here we possibly branch left, middle and right with multiple keys.
            // It is possible that the partition has split the keys
            // and the recursion proceeds with a reduced set in each region.
            //                   p0 p1               p2 p3
            // |l|--|ka|--k----k--|P|------k--|kb|----|P|----|r|
            //                 kb  |      ka
            f += RECURSION_INCREMENT;
            // Recurse left side if required
            if (ka < p0) {
                if (kb <= p1) {
                    // Entirely on left side
                    r = p0 - 1;
                    if (r < kb) {
                        kb = k.updateRight(r);
                    }
                    continue;
                }
                dualPivotQuickSelect(a, l, p0 - 1, k.splitLeft(p0, p1), f);
                // Here we must process middle and/or right
                ka = k.left();
            } else if (kb <= p1) {
                // No middle/right side
                return;
            } else if (ka <= p1) {
                // Advance lower bound
                ka = k.updateLeft(p1 + 1);
            }
            // Recurse middle if required
            final int p2 = upper[1];
            final int p3 = upper[2];
            if (ka < p2) {
                l = p1 + 1;
                if (kb <= p3) {
                    // Entirely in middle
                    r = p2 - 1;
                    if (r < kb) {
                        kb = k.updateRight(r);
                    }
                    continue;
                }
                dualPivotQuickSelect(a, l, p2 - 1, k.splitLeft(p2, p3), f);
                ka = k.left();
            } else if (kb <= p3) {
                // No right side
                return;
            } else if (ka <= p3) {
                ka = k.updateLeft(p3 + 1);
            }
            // Continue right
            l = p3 + 1;
        }
    }