I understand your intellectual curiosity wrt the algorithm, but my post was more a subtle hint that using a pre-packaged wheel is often a better way of spending time than polishing your own variant. Seems from OP's reply I picked the right answer.

From the benchmark results I guessed XS was likely lurking in the background somewhere, but in this case that can be treated as a reasonable optimisation by the module author. There is no hint in the List::Util docs that indicate the implementation method, however the guts of the routine seems to be:

    for (index = items ; index > 1 ; ) {
    int swap = (int)(Drand01() * (double)(index--));
    SV *tmp = ST(swap);
    ST(swap) = ST(index);
    ST(index) = tmp;
    }
    XSRETURN(items);
[download]