Sorting large arrays

From HaskellWiki
Revision as of 23:14, 22 December 2009 by DonStewart (talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

An example of how to efficiently sort large arrays in native Haskell, using the uvector array type, and the uvector-algorithms package.

This is an in-place sort, using destructive updates in the ST (i.e. mutable memory) monad.

{-

Sort 10M floats in 1.4s in pure Haskell.
Uses uvector and uvector-algorithms.

-}

import Control.Monad.ST
import Data.Array.Vector
import Data.Array.Vector.Algorithms.Merge

main = do
    let e = runST (do
                v <- newMU (10^7) :: ST s (MUArr Float s)
                sort v
                readMU v 0)
    print e

It presents the smallest element of the array after sorting.

Compiling:

   ghc -O2 --make A.hs

Running:

   $ time ./A
   0.0
   ./A  1.22s user 0.04s system 98% cpu 1.278 total