>>643の場合を、quick sortで考えてみる。
中央値はランダムに決定されることは自明だと思うので省略。
残りの要素はランダムに振り分けられるので、左右どちらに行くかは等確率。
これを再帰的に繰り返せば全体も等確率と考えていいんじゃないかな。
ただ、最後はselection sortを使ってるんで、これは等確率じゃないような気がする。
n個の要素から最小値を選び出す場合、最初に比較された要素が選ばれる確率は
2**(1-n)だけど、最後に比較されたものが選ばれる確率は1/2。

おまけ
def tossup
  rand(2)*2-1
end