1 files changed, 43 insertions, 0 deletions
diff --git a/Sort/Sort.hs b/Sort/Sort.hs
new file mode 100644
index 0000000..2dc15a6
--- /dev/null
+++ b/Sort/Sort.hs
@@ -0,0 +1,43 @@
+module Sort.Sort (qsort,msort,msortBy) where
+
+import Control.Parallel
+import Criterion.Main
+import System.Random
+import Control.DeepSeq
+
+main = defaultMain
+    [bench "qsort" (nf qsort randomInts),
+    bench "pqsort" (nf pqsort randomInts)]
+
+qsort (x:xs) = [a | a<-xs, a<=x] ++(x:[a | a<-xs, a>x])
+
+pqsort (x:xs) = par (rnf larg) ([a|a<-xs, a<=x]++(x:larg))
+    where larg = [a|a<-xs,a>x]
+
+randomInts = take 200000 (randoms (mkStdGen 211570155)) :: [Integer]
+
+msort xs = msortBy compare xs
+
+msortBy cmp xs = mergeAll $ warp xs
+    where
+        warp (a:b:xs)
+            | a `cmp` b /= GT = let (dec,rst) = decwarp xs [b,a] in dec:warp rst
+            | otherwise = let (inc,rst) = incwarp xs [b,a] in (reverse inc):warp rst
+        warp t = [t]
+        decwarp xx@(x:xs) aa@(a:as) 
+            | a `cmp` x /= LT = decwarp xs (x:aa)
+            | otherwise = (aa,xx)
+        decwarp [] aa = (aa,[])
+        incwarp xx@(x:xs) aa@(a:as) 
+            | a `cmp` x /= GT = incwarp xs (x:aa)
+            | otherwise = (aa,xx)
+        incwarp [] aa = (aa,[])
+        merge (a:b:xs) = (mergePair a b []):(merge xs)
+        merge xs = xs
+        mergeAll [x] = x
+        mergeAll xs = mergeAll $ merge xs
+        mergePair [] bs os = (reverse os) ++ bs
+        mergePair as [] os = (reverse os) ++ as
+        mergePair aa@(a:as) bb@(b:bs) os
+            | b `cmp` a == GT = mergePair as bb (a:os)
+            | otherwise = mergePair aa bs (b:os)