>>884
確かにそうだ。最悪O(n^2)になるな。
でも、中間リストを作ることが直接の原因ではない。
実際、正確評価ならelts_lt_xとelts_greq_xを作り終えた時点で引数のxsはGCできる。
遅延評価だとこれが上手くいかなくて、逆順にソートされたリストが渡される最悪のケースでO(n^2)になる。
時間的には同じ最悪のケースでも、入力が正順にソートされていた場合はO(n)なんだが。

汚い方法だけど、seqを使って評価順を入れ替えることでO(n)になる。
qsort [] = []
qsort (x:xs) = length elts_lt_x `seq` length elts_greq_x `seq`
  qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
  where
    elts_lt_x = [y | y <- xs, y < x]
    elts_greq_x = [y | y <- xs, y >= x]