[Haskell-cafe] (flawed?) benchmark : sort

[Neil Mitchell]

Hi

>  -- 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.

Thanks

Neil