2 ms·
Let us convince ourselves that sort sorts: GHCi, version 6.12.1: http://www.haskell.org/ghc/ http://www.haskell.org/ghc/ :? for help Loading package ghc-prim
by thesz 15y ago
Let us convince ourselves that sort sorts:
GHCi, version 6.12.1: http://www.haskell.org/ghc/ http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
Prelude> :m Data.List -- for sort function
Prelude Data.List> :se +s -- to display timings.
Prelude Data.List> last $ sort [1..2^20]
1048576
(1.34 secs, 544634924 bytes)
Prelude Data.List> last $ sort [1..2^21]
2097152
(2.84 secs, 1125744400 bytes)
Prelude Data.List> last $ sort [1..2^22]
4194304
(5.51 secs, 2325062504 bytes)
Prelude Data.List> 1.34/(2^20)/20
6.389617919921875e-8
(0.02 secs, 1576728 bytes)
Prelude Data.List> 2.84/(2^21)/21
6.44865490141369e-8
(0.00 secs, 1578108 bytes)
Prelude Data.List> 5.51/(2^22)/22
5.971301685680042e-8
(0.00 secs, 1572220 bytes)
Looks like it really sorts, even strictly ascending sequence (2^22 time problems could be attributed to GC or something).
Let us take first N from sorted list:
Prelude Data.List> sum $ take (2^1) $ sort [1..2^22]
3
(2.25 secs, 760208692 bytes)
Prelude Data.List> sum $ take (2^2) $ sort [1..2^22]
10
(2.50 secs, 760292356 bytes)
Prelude Data.List> sum $ take (2^3) $ sort [1..2^22]
36
(2.25 secs, 759678188 bytes)
Prelude Data.List> sum $ take (2^4) $ sort [1..2^22]
136
(2.51 secs, 760209208 bytes)
Prelude Data.List> sum $ take (2^5) $ sort [1..2^22]
528
(2.36 secs, 759678236 bytes)
Prelude Data.List> sum $ take (2^6) $ sort [1..2^22]
2080
(2.31 secs, 759682904 bytes)
I don't know why this looks almost constant. But it is!
I expected to be able to show O(nlogk), but it performed even better. ;)