List.sort

[Ian Lynagh]

On Sun, May 12, 2002 at 09:22:02PM +0100, Claus Reinke wrote:
> 
> > randomise l = do
> >   map snd $ sortBy compareIdx $ zip rs l
> >   where
> >     n  = length l
> >     rs = take n $ randomRs (1,n) $ mkStdGen 100
> >     compareIdx (i,_) (j,_) = i `compare` j
> 
> > rsort l = sort $ randomise l

This algorithm doesn't have the stable property, but it can be easily
adapted with:

> srandomise l = do
>   map fst $ map snd $ sortBy compareIdx $ zip rs $ zip l ([1..] :: Integer)
>   where
>     n  = length l
>     rs = take n $ randomRs (1,n) $ mkStdGen 100
>     compareIdx (i,_) (j,_) = i `compare` j

> rssort l = sort $ srandomise l

Out of curiousity I also tried:

> sxrandomise l = do
>   map fst $ map snd $ sortBy compareIdx $ zip rs $ zip l ([1..] :: Integer)
>   where
>     rs = randoms $ mkStdGen 100
>     compareIdx (i,_) (j,_) = i `compare` j

> rsxsort l = sort $ sxrandomise l

Of course if you use 100 as the seed then rsxsort does poorly on the
random_list test as it first sorts the input and then sorts the sorted
input, giving

stdin           10000            random_list   rsxsort     21.90
func            10000            random_list   rsxsort     27.21

The results using 200 as a seed are shown below (I removed stdin/100000
as they were all *s again). mergesort has the edge, but you'd expect
that as r*sort aren't going to get perfect splits. r*sort should do
better if there were lots of repeated inputs.

Input style     Input length     Sort data     Sort alg    User time
stdin           10000            random_list   sort        2.85
stdin           10000            random_list   rsort       2.98
stdin           10000            random_list   rssort      3.04
stdin           10000            random_list   rsxsort     3.18
stdin           10000            random_list   mergesort   3.02
stdin           10000            sorted        sort        31.09
stdin           10000            sorted        rsort       2.05
stdin           10000            sorted        rssort      2.09
stdin           10000            sorted        rsxsort     2.20
stdin           10000            sorted        mergesort   1.88
stdin           10000            revsorted     sort        31.17
stdin           10000            revsorted     rsort       2.04
stdin           10000            revsorted     rssort      2.10
stdin           10000            revsorted     rsxsort     2.17
stdin           10000            revsorted     mergesort   1.85
func            10000            random_list   sort        0.30
func            10000            random_list   rsort       0.94
func            10000            random_list   rssort      1.05
func            10000            random_list   rsxsort     1.14
func            10000            random_list   mergesort   0.91
func            10000            sorted        sort        19.28
func            10000            sorted        rsort       0.30
func            10000            sorted        rssort      0.37
func            10000            sorted        rsxsort     0.44
func            10000            sorted        mergesort   0.16
func            10000            revsorted     sort        19.30
func            10000            revsorted     rsort       0.30
func            10000            revsorted     rssort      0.37
func            10000            revsorted     rsxsort     0.48
func            10000            revsorted     mergesort   0.15
func            100000           random_list   sort        3.97
func            100000           random_list   rsort       *
func            100000           random_list   rssort      *
func            100000           random_list   rsxsort     *
func            100000           random_list   mergesort   *
func            100000           sorted        sort        5873.15
func            100000           sorted        rsort       5.25
func            100000           sorted        rssort      5.66
func            100000           sorted        rsxsort     6.29
func            100000           sorted        mergesort   2.18
func            100000           revsorted     sort        5828.57
func            100000           revsorted     rsort       5.13
func            100000           revsorted     rssort      5.57
func            100000           revsorted     rsxsort     6.45
func            100000           revsorted     mergesort   2.24