O(n)で可能であると思われます。
ttp://kukuli.jp/haskell/qsort.zip