Is there any function in haskell libraries that sorts integers in O(n) time?? [By, O(n) I mean faster than comparison sort and specific for integers]

Basically I find that the following code takes a lot of time with the sort (as compared to summing the list without sorting) :

```
import System.Random
import Control.DeepSeq
import Data.List (sort)

genlist gen = id $!! sort $!! take (2^22) ((randoms gen)::[Int])

main = do
    gen <- newStdGen
    putStrLn $ show $ sum $ genlist gen

```

Summing a list doesn't require deepseq but what I am trying for does, but the above code is good enough for the pointers I am seeking. 

Time : 6 seconds (without sort); about 35 seconds (with sort)

Memory : about 80 MB (without sort); about 310 MB (with sort)

**Note 1 :** memory is a bigger issue than time for me here as for the task at hand I am getting out of memory errors (memory usage becomes 3GB! after 30 minutes of run-time)

I am assuming faster algorithms will provide bettor memory print too, hence looking for O(n) time.

**Note 2 :** I am looking for fast algorithms for Int64, though fast algorithms for other specific types will also be helpful.

---

**Solution Used :** IntroSort with unboxed vectors was good enough for my task:

```
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Algorithms.Intro as I

sort :: [Int] -> [Int]
sort = V.toList . V.modify I.sort . V.fromList

```