pixie-lang
diff --git a/pixie/stdlib.pxi b/pixie/stdlib.pxi
@@ -2974,3 +2974,42 @@ ex: (vary-meta x assoc :foo 42)"
    :added "0.1"}
   [x f & args]
   (with-meta x (apply f (meta x) args)))
+
+(defn trampoline [f]
+  (let [result (f)]
+    (if (fn? result)
+      (recur result)
+      result)))
+
+;;; Sorting
+
+(defn -merge-sort-step
+  [comp-fn merged-left merged-right res]
+  (cond 
+    (empty? merged-left) (into res merged-right) 
+    (empty? merged-right) (into res merged-left) 
+    :else
+    (if (neg? (comp-fn (first merged-left) (first merged-right)))
+      (recur comp-fn (rest merged-left) merged-right (conj res (first merged-left)))
+      (recur comp-fn merged-left (rest merged-right) (conj res (first merged-right))))))
+
+(defn -merge-sort-split
+  [comp-fn coll]
+  (if (> (count coll) 1)
+    (let [[left right] (split-at (/ (count coll) 2) coll)]
+      (-merge-sort-step comp-fn 
+                        (trampoline #(-merge-sort-split comp-fn left)) 
+                        (trampoline #(-merge-sort-split comp-fn right)) 
+                        [])) 
+    coll))
+
+(defn merge-sort [comp-fn coll]
+  (-merge-sort-split comp-fn coll))
+
+(defn sort 
+  ([coll]
+   (sort compare coll))
+  ([comp-fn coll]
+   (merge-sort comp-fn coll)))
+
+;;; End Sorting
diff --git a/pixie/test-sort.pxi b/pixie/test-sort.pxi
@@ -0,0 +1,11 @@
+(ns pixie.tests.test-sort
+  (require pixie.test :as t))
+
+(t/deftest test-sort
+  (t/assert= (sort [5 2 3 1 4]) [1 2 3 4 5])
+  (t/assert= (sort ["d" "c" "b" "a"]) ["a" "b" "c" "d"])
+  (t/assert= (sort [1/1 1/2 1/3 1/4]) [1/4 1/3 1/2 1/1]))
+
+(t/deftest test-sort-big
+  (t/assert= (sort (range 10000))      (range 10000))
+  (t/assert= (sort (range 9999 -1 -1)) (range 10000)))