In Haskell
Mergesort requires O(1) index access so I used Data.Vector instead of List.
import qualified Data.Vector as V
-- length (sort2 x y) == 2
-- sorted (sort2 x y) is true
sort2 :: Ord a => a -> a -> V.Vector a
sort2 x y = if x < y then V.fromList [x, y] else V.fromList [y, x]
-- contract: sorted xs && sorted ys
-- length (merge xs ys) == length xs + length ys
-- sorted (merge xs ys) is true
merge :: Ord a => V.Vector a -> V.Vector a -> V.Vector a
merge xs ys = case (xs V.!? 0, ys V.!? 0) of
(Nothing, _) -> ys
(_, Nothing) -> xs
(Just x, Just y) -> if x < y
then x `V.cons` merge (V.tail xs) ys
else y `V.cons` merge xs (V.tail ys)
-- length (mergeSort xs) == length xs
-- sorted (mergeSort xs) is true
mergeSort' :: Ord a => V.Vector a -> V.Vector a
mergeSort' xs = case V.length xs of
0 -> xs
1 -> xs
2 -> sort2 (V.head xs) (V.last xs)
otherwise -> let (a, b) = split2 xs in
merge (mergeSort' a) (mergeSort' b)
mergeSort :: Ord a => [a] -> [a]
mergeSort = V.toList . mergeSort' . V.fromList
-- contract: length xs > 2
-- (a, b) = split2 xs => length a + length b == length xs
split2 :: Ord a => V.Vector a -> (V.Vector a, V.Vector a)
split2 xs = (V.take (V.length xs `div` 2) xs, V.drop (V.length xs `div` 2) xs)
main = do
print $ mergeSort [3, 1, 4, 1, 5, 9, 2]
In Clojure
(defn sort2 [x y]
(if (< x y) [x y] [y x]))
(defn merge2 [xs ys]
(cond
(empty? xs) ys
(empty? ys) xs
:else
(let [x (first xs) y (first ys)]
(if (< x y)
(cons x (merge2 (rest xs) ys))
(cons y (merge2 (rest ys) xs))))))
(defn merge-sort [xs]
(cond
(> 2 (count xs)) xs
(= 2 (count xs)) (apply sort2 xs)
:else (let [[a b] (split-at (/ (count xs) 2) xs)]
(merge2 (merge-sort a) (merge-sort b)))))
(prn (merge-sort [3 1 4 1 5 9 2]))
Scheme (Gauche)
With List (slow)
(use srfi-1)
(define (sort2 x y)
(if (< x y) (list x y) (list y x)))
(define (nil? xs)
(eq? xs '()))
(define (merge2 xs ys)
(cond
((nil? xs) ys)
((nil? ys) xs)
((let ((x (car xs))
(y (car ys)))
(if (< x y)
(cons x (merge2 (cdr xs) ys))
(cons y (merge2 xs (cdr ys))))))))
(define (merge-sort xs)
(cond
((> 2 (length xs)) xs)
((= 2 (length xs)) (apply sort2 xs))
((receive (a b) (split-at xs (/ (length xs) 2))
(merge2 (merge-sort a) (merge-sort b))))))
(print (merge-sort '(3 1 4 1 5 9 2 6)))
With Vector (fast)
(use srfi-43)
(define (sort2 x y)
(if (< x y) (vector x y) (vector y x)))
(define (merge2 xs ys)
(cond
((vector-empty? xs) ys)
((vector-empty? ys) xs)
((let ((x (~ xs 0))
(y (~ ys 0)))
(if (< x y)
(vector-append (vector x) (merge2 (vector-copy xs 1 -1) ys))
(vector-append (vector y) (merge2 xs (vector-copy ys 1 -1))))))))
(define (merge-sort xs)
(cond
((> 2 (vector-length xs)) xs)
((= 2 (vector-length xs)) (sort2 (~ xs 0) (~ xs 1)))
((let ((a (vector-copy xs 0 (div (vector-length xs) 2)))
(b (vector-copy xs (div (vector-length xs) 2) -1)))
(merge2 (merge-sort a) (merge-sort b))))))
(print (merge-sort #(3 1 4 1 5 9 2 6)))
