[Haskell-cafe] (flawed?) benchmark : sort
ndmitchell at gmail.com
Tue Mar 4 12:54:21 EST 2008
> -- Zadanie 9 - merge sort
> mergeSort :: Ord a => [a] -> [a]
> mergeSort  = 
> mergeSort [x] = [x]
> mergeSort xs = let(l, r) = splitAt (length xs `quot` 2) xs
> in mergeSortP (mergeSort l) (mergeSort r)
splitAt is not a particularly good way to split a list, since you
recurse over the list twice. Try instead:
split (x:xs) = (x:b,a)
where (a,b) = split xs
split  = (, )
Perhaps adding some strictness annotations and turning the where into a case.
Also remember that a standard benchmark for sorting is an
ordered/reverse ordered list, as that causes quicksort to go to O(n^2)
given a bad pivot choice.
If the sort in the standard libraries can be improved on, it should be replaced.
More information about the Haskell-Cafe