ghc-5.04 sort not stable?

[Ralf Hinze]

Am Samstag, 20. Juli 2002 17:42 schrieb Jon Fairbairn:
> The library report says
>
>    sort/sortBy implement a stable sorting algorithm
>
> In ghc 5.02.3
>
> List.sortBy (\(a,b) (a',b')->compare a a')
> ([1,1,1,1,1,1,1,1,1,1]`zip`[1..10])
>
> gives [(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(1,10)]
>
> but in 5.04
>
> gives [(1,10),(1,9),(1,8),(1,7),(1,6),(1,5),(1,4),(1,3),(1,2),(1,1)]

The merge routine is not stable (in fptools/libraries/base/Data/List.hs).
Fix: replace

merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
merge cmp xs [] = xs
merge cmp [] ys = ys
merge cmp (x:xs) (y:ys)
 = case x `cmp` y of
        LT -> x : merge cmp    xs (y:ys)
        _  -> y : merge cmp (x:xs)   ys

by

merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
merge cmp xs [] = xs
merge cmp [] ys = ys
merge cmp (x:xs) (y:ys)
 = case x `cmp` y of
        GT -> y : merge cmp (x:xs)   ys
        _  -> x : merge cmp    xs (y:ys)

Cheers, Ralf