どこかで見た問題と思ったら結城さんのところで見た問題だった.
後者の証明はid:shinichiro_hさんがされている.
また,ランダム値を与えてソートする方法がコメント欄で指摘されているけどもも,その問題点は工藤さんが以前書かれていた.
乱数を与えても同じ値を与えてしまうと,ソートを正確に行えない.stable sortだとシャッフル前の順序を保ってしまうし,unstableであっても結果は固定的なのでランダムにはならないからである.同じ値を与えた部分に対してさらにシャッフルをしなくてはならないので問題がループしてしまっているように思える.
乱数の実装まで考慮するとFischer-Yates Shuffleも偏りが存在すると思うのだけども,アルゴリズムの正確さと速度の面からFischer-Yates Shuffleの方が良さげ.