フィッシャー–イェーツのシャッフル
マージソートのような違ったソート法でランダムな比較を使用した場合、より均一な結果を取得できることもある。しかしそれも完全ではない。マージソートの場合、二つの数列の中からどちらかの数値を同確率で選択していくことで、その数列を結合する。この「コイントス」のような、2通りからランダムに取得する手法を繰り返す場合、(数列が2よりも大きい場合は)均一な分布となることはない。なぜなら、この方法による、ある順列が生成される確率は2の階乗を分母とする値であるはずであり、求められている確率は 1/n! となるからである。
そしてこのシャッフル方法は、原理的に無限ループやアクセス違反などのプログラム実行時のエラーを引き起こすことさえある。なぜなら、ソートアルゴリズムがランダムに動作する場合は順序関係(例えば推移関係)が正しく提供されないためである。 以前の比較結果に依存するような、確実に結果が予測されうるような比較を行うような振る舞いはソートの手順の中で行われるべきではないが、意図的にこのような比較を行う明確な理由がある場合は別である。例えば、効率化のために、番兵として自分自身との比較を行うような場合は、ランダムな比較関数はこのソートのアルゴリズムを破壊するだろう。
フィッシャー–イェーツのシャッフルは極めて効率的であり、時間的空間的な計算量は最適である。偏りのない良質な乱数をもとにするならば、生成結果も偏りがないことが保証される。他のアルゴリズムと比較してもその長所は変わらない。もしも結果の順列の一部のみが必要であれば、必要な数の順列が生成された時点で処理を中断すればよい。
異なるシャッフルの手法としては、集合のそれぞれの要素にランダムな番号を付与し、その後にそれらをソートする方法がある。ソートによる手法は、フィッシャー–イェーツのシャッフルとは時間的計算量は同一である。ただし、一般的なソート法の計算量は O(n log n) であり、効果的に処理するためには時間的計算量が O(n) の基数ソートを用いる必要がある。ソートによる手法も、フィッシャー–イェーツのシャッフルと同じく偏りのない結果を生成するが、ランダムな番号を付与する際に重複しないように注意しなければならない。なぜならソートのアルゴリズムは同じ値の要素を並べる際はランダムにならないからである。さらにこの手法では、付与する番号のために空間的計算量 O(n) となる追加領域を必要とする。対してフィッシャー–イェーツのシャッフルでは O(1) である。