Mergesort in Haskell, Clojure and Scheme

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)))