1万行近くあるデータをランダムにソートしたいとき、
トランプを切るときみたいに、ランダムに決めた位置で
上半分と下半分をひっくり返すというのを繰り返すのはどうでしょうか？
プログラムが簡単なんでどうかと思いますが、よくないでしょうか？