Ticket #2143: SortBy.hs

File SortBy.hs, 855 bytes (added by malcolm.wallace@…, 5 years ago)

A stable O(n log n) sorting algorithm, by Thomas Nordin, 2002

Line 
1module List where
2
3-- stable sorting algorithm
4
5sortBy :: (a -> a -> Ordering) -> [a] -> [a]
6sortBy cmp = mergeAll . sequences
7  where
8    sequences (a:b:xs)
9      | a `cmp` b == GT = descending b [a]  xs
10      | otherwise       = ascending  b (a:) xs
11    sequences xs = [xs]
12
13    descending a as (b:bs)
14      | a `cmp` b == GT = descending b (a:as) bs
15    descending a as bs  = (a:as): sequences bs
16
17    ascending a as (b:bs)
18      | a `cmp` b /= GT = ascending b (\ys -> as (a:ys)) bs
19    ascending a as bs   = as [a]: sequences bs
20
21    mergeAll [x] = x
22    mergeAll xs  = mergeAll (mergePairs xs)
23
24    mergePairs (a:b:xs) = merge a b: mergePairs xs
25    mergePairs xs       = xs
26
27    merge as@(a:as') bs@(b:bs')
28      | a `cmp` b == GT = b:merge as  bs'
29      | otherwise       = a:merge as' bs
30    merge [] bs         = bs
31    merge as []         = as