Improving naive qsort implementation

Question

I am starting to learn Haskell and I read this page on the Haskell wiki which reports on this qsort implementation:

qsort :: (Ord a) => [a] -> [a] qsort [] = [] qsort (x:xs) = qsort less ++ [x] ++ qsort more where less = filter (<x) xs more = filter (>=x) xs 

and then a warning that this is not the most efficient way to do this, and an article link that shows an incredibly detailed version of the same algorithm. Just by looking at it, I, although this is not what I studied Haskell, and I wanted to make a better version of the original qsort, without sacrificing my elegance. I mainly focused on eliminating the need to run filter twice every call, and this is what I came up with:

 filter' :: (a -> Bool) -> [a] -> ([a], [a]) filter' _ [] = ([], []) filter' fa = filterInternal a ([], []) where filterInternal [] p = p filterInternal (x:xs) (l, t) | fx = filterInternal xs (x:l, t) | otherwise = filterInternal xs (l, x:t) qsort' :: (Ord a) => [a] -> [a] qsort' [] = [] qsort' (x:xs) = qsort' less ++ [x] ++ qsort' more where (more, less) = filter' (>x) xs 

But I'm not sure if this is really better. I mean, it works, but how does it compare with the original version?

Answer 1

Here is a solution that I came up with, thinking about the same problem (please indicate any reservations!). I didn't think too much about the complexity of the space (it shouldn't be too scary, though), just the time. What really kills naive qsort is the O(n) (++) operation. So, let's use a new data structure (which will add up) that gives us fast concatenation.

 {-# LANGUAGE DeriveFoldable #-} import Data.Foldable import Data.List data Seq a = (Seq a) :++: (Seq a) | Leaf a | Empty deriving (Foldable) 

Then the modified qsort' , which returns a Seq a , will be

 qsort' :: Ord a => [a] -> Seq a qsort' [] = Empty qsort' (x:xs) = qsort less :++: Leaf x :++: qsort more where (less, more) = partition (<x) xs 

And qsort itself then just qsort = toList . qsort' qsort = toList . qsort' .

Note. A fix that includes partition gives you a constant coefficient better, but ++ vs :++: means qsort can now be better than O(n^2) . In addition, most implementations there are better than this. The point is to try to accurately reflect the "naive" implementation.