4 Mar
2008
4 Mar
'08
5:54 p.m.
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