Ralf wrote:
100000 | < | <= | > | >= | == | 1 2* |
1..100* | 2 1* | 100..1* | 1 2 2 1* | random
merge | 3.15 | 9.16 | 2.83 | 8.96 | 3.18 | 6.65 |
9.60 | 6.64 | 9.46 | 6.58 | oo
bottom-up | 2.18 | 7.73 | 1.99 | 7.60 | 2.17 | 4.74 |
13.01 | 4.63 | 12.51 | 4.59 | oo
heap | oo | oo | oo | oo | 17.90 | oo |
oo | oo | oo | oo | oo
pairing | 1.20 | 2.53 | 1.58 | 3.93 | 1.28 | 2.25 |
3.93 | 2.24 | 4.07 | 2.23 | 9.87
Jon's | 0.95 | 2.73 | 0.93 | 2.90 | 2.18 | 3.00 |
3.54 | 3.06 | 3.51 | 2.78 | 8.63
braun | 21.87 | oo | 21.77 | oo | 7.66 | 14.67 |
20.93 | 14.93 | 21.00 | 14.65 | 23.01
smooth | 0.22 | 0.41 | 0.17 | 6.77 | 0.20 | 4.49 |
3.25 | 4.43 | 3.21 | 4.40 | oo
oo = heap or stack overflow
1. | smooth | smooth | smooth | Jon's | smooth | pairing |
smooth | pairing | smooth | pairing | Jon's
2. | Jon's | pairing | Jon's | pairing | pairing | Jon's |
Jon's | Jon's | Jon's | Jon's | pairing
3. | pairing | Jon's | pairing | smooth | bottom-up | smooth |
pairing | smooth | pairing | smooth | braun
4. | bottom-up | bottom-up | bottom-up | bottom-up | Jon's | bottom-up |
merge | bottom-up | merge | bottom-up |
5. | merge | merge | merge | merge | merge | merge |
bottom-up | merge | bottom-up | merge |
6. | braun | | braun | | braun | braun |
braun | braun | braun | braun |
7. | | | | | heap | braun |
| | | |
Well, I'm a sucker for a benchmark so I ran all of these with hbc.
I also added the smooth merge sort that comes with hbc.
Here is my table (for 100000 elements)
< <= > >= == 1 2* 1..100* 2 1* 100..1* 1 2 2 1*
random
merge 2.050 5.124 2.108 5.336 2.059 2.817 3.043 2.801 3.026 2.792
3.702
bumerge 1.155 3.025 1.187 3.121 1.226 2.019 2.185 1.983 2.175 1.932
2.894
heap 5.939 14.252 5.949 14.301 4.140 4.678 5.557 4.694 5.627 4.629
6.239
pair 0.533 1.582 0.938 2.431 0.570 1.178 2.269 1.174 2.392 1.224
4.356
jon 0.839 1.926 0.856 2.055 1.841 2.667 3.185 2.685 3.172 2.463
7.173
braun 7.850 18.270 8.014 18.574 4.556 6.606 7.685 6.658 7.648 6.606
8.362
smooth 0.183 0.425 0.165 3.454 0.180 2.071 1.431 1.969 1.403 1.942
3.018
hbc 0.124 0.321 1.346 2.592 0.136 1.839 1.367 2.026 2.331 1.856
2.798
1 hbc hbc smooth jon hbc pair hbc pair smooth pair
hbc
2 smooth smooth jon pair smooth hbc smooth bumerge bumerge hbc
bumerge
3 pair pair pair hbc pair smooth pair smooth hbc
bumerge smooth
As you can see there is no clear winner, but I see no real reason
to change the sort that comes with hbc to something else at this
moment.
All my tests were on a PC with a 200MHz Pentium Pro.
-- Lennart
> sortHbc :: (Ord a) => [a] -> [a]
> sortHbc [] = []
> sortHbc (x:xs) = msort (upSeq xs [x])
>
> upSeq [] xs = [reverse xs]
> upSeq (y:ys) xxs@(x:xs) =
> if x <= y then
> upSeq ys (y:xxs)
> else
> reverse xxs : upSeq ys [y]
>
> msort [xs] = xs
> msort xss = msort (mergePairs xss)
>
> mergePairs (xs:ys:xss) = merge xs ys : mergePairs xss
> mergePairs xss = xss
>
> merge xxs@(x:xs) yys@(y:ys) =
> if x <= y then
> x:merge xs yys
> else
> y:merge xxs ys
> merge [] yys = yys
> merge xxs [] = xxs