id:sawat:20061123の記述に関して。 クイックソートとマージソートの話で、クイックソートは安定でないということが書かれているが、そういう風に書くとさすがに嘘じゃないか?と思ったので。安定と言うのはこの場合、リスト中に同じ大きさの要素があった場合に、その順序が入れ替わらないことを言う。 クイックソートで第一に重要になるのはピボット選択(つまり、比較対象の選択)だが、これをもし仮にリスト(or配列)の中から取ってくるとすると、その値をどこに入れるのか。その作業で不安定になることがある。しかし、クイックソートはリストの対象を二つに分割するわけだが、その操作においては安定であるようにすることが可能である。例えばHaskellなどでよく使われるクイックソートは、 quicksort :: Ord a => [a] -> [a] quicksort = quicksort (x:xs)