Compiling with -O3 using
quicksort [] = [] quicksort (x : xs) = quicksort (filter (< x) xs) ++ [x] ++ quicksort (filter (>= x) xs)
1.1 times slower than a program using
quicksort2 [] = [] quicksort2 (x : xs) = quicksort2 [y | y <- xs, y < x] ++ [x] ++ quicksort2 [y | y <- xs, y >= x]
6 times slower than a program using
minisort [] = [] minisort xs = let x = minimum xs in x : minisort (delete x xs)
This is not a Haskell-native sort merge and should not be.
I noticed that minisort sequentially runs much faster than both quicksort s, which seemed understandable given the complexity of the operations involved. What I don't understand is a consistent little edge quicksort2 has more quicksort . Are list views more efficient than filter expressions?
The ones I used so far have been a criterion , with nf , ghci :set +s and two remote performance functions, ( ideone , rextester ).
comparison criterion: worst case [5000, 4999 .. 1] :: [Int] :
benchmarking quicksort time 2.283 s (2.191 s .. 2.450 s) 0.999 R² (0.998 R² .. 1.000 R²) mean 2.434 s (2.368 s .. 2.485 s) std dev 79.23 ms (0.0 s .. 88.75 ms) variance introduced by outliers: 19% (moderately inflated) benchmarking quicksort2 time 2.203 s (1.982 s .. 2.455 s) 0.998 R² (0.994 R² .. 1.000 R²) mean 2.327 s (2.275 s .. 2.359 s) std dev 49.11 ms (0.0 s .. 56.47 ms) variance introduced by outliers: 19% (moderately inflated) benchmarking minisort time 257.2 ms (229.7 ms .. 276.4 ms) 0.997 R² (NaN R² .. 1.000 R²) mean 274.4 ms (264.3 ms .. 280.9 ms) std dev 9.714 ms (2.538 ms .. 12.94 ms) variance introduced by outliers: 16% (moderately inflated)
quicksort2 always (various test cases, orders, and contexts) performs a bit better than quicksort . minisort is definitely better than both of them.