3 ms·

Technically the quicksort at the end of the tutorial isn't idiomatic quicksort, the memory complexity is wrong.

• quchen 13y ago
  Even for linked lists, which is how [] is defined in Haskell?
  • taeric 13y ago
    I believe the idea is that if it is not "in place," it is not quick sort.
    • nandemo 13y ago
      That's right. That Haskell faux-quicksort uses a lot of extra space for the temporary lists. Here's a Haskell version of the "real" quicksort, though it isn't nearly easy a read as the faux-quicksort: http://augustss.blogspot.jp/2007/08/quicksort-in-haskell-quicksort-is.html http://augustss.blogspot.jp/2007/08/quicksort-in-haskell-qui... For what is worth, the standard Haskell sort is a variant of merge sort. http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/Data-List.html#sort http://hackage.haskell.org/packages/archive/base/latest/doc/...
• egonschiele 13y ago
  Correct. Sadly explaining monads and mutable data in Haskell would make this guide a lot longer. The example I gave is the traditional "look has elegant Haskell is!" example, not the "look how fast Haskell is!" example :)
  • DanWaterworth 13y ago
    You could use mergesort instead: merge :: Ord x => [x] -> [x] -> [x] merge [] y = y merge x [] = x merge (x:xs) (y:ys) = if x < y then x:(merge xs (y:ys)) else y:(merge (x:xs) ys) odds :: [x] -> [x] odds [] = [] odds (x:xs) = x:(evens xs) evens :: [x] -> [x] evens = odds . drop 1 mergesort :: Ord x => [x] -> [x] mergesort [] = [] mergesort [x] = [x] mergesort x = merge (mergesort (odds x)) (mergesort (evens x))