Fastest way to partition array, given a condition

General Usage Performance
8

This should minimize the number of swaps but the overall higher complexity doesn’t seem to pay off unless the swaps are more expensive than in the benchmark.

function partialsort_cutoff2!(x, cutoff)
    i, j = extrema(eachindex(x))
    while true
        while i < j && x[i] <= cutoff
            i += 1
        end
        while j > i && x[j] > cutoff
            j -= 1
        end
        if j <= i
            return i - 1
        end
        x[i], x[j] = x[j], x[i]
    end
end

Edit: There’s a corner case bug if all elements are lower than the cutoff.

1 Like