とりあえず、よくあるもっとも簡単な実装はこれかな。

qs :: (Ord a) => [a] -> [a]
qs [] = []
qs (x:xs) = qs (filter (< x) xs) ++ [x] ++ qs (filter (> x) xs)

空間計算量が最悪O(n^2)になるケースってのは、どういうリストに適用した時？