Skip to content

Instantly share code, notes, and snippets.

@klapaucius
Created October 27, 2011 09:31
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save klapaucius/1319163 to your computer and use it in GitHub Desktop.
Save klapaucius/1319163 to your computer and use it in GitHub Desktop.
in-place quick sort
import Data.Vector.Generic
import qualified Data.Vector.Generic.Mutable as M
iqsort :: (Vector v a, Ord a) => v a -> v a
iqsort = modify go where
go xs | len < 2 = return ()
| otherwise = do
p <- xs `M.read` (len `div` 2)
m <- M.unstablePartition (< p) xs
go $ M.slice 0 m xs
go $ M.slice (m+1) (len-m-1) xs
where len = M.length xs
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment