# This Baskell module implements insertion sort and merge sort
# for lists of ints.
#
# Author: Bernie Pope
# Date:   12 October 2004

isort  
   = !list -> 
        ite (null list) 
            list 
            (insert (head list) (isort (tail list)));

insert 
   = !x -> !list -> 
        ite (null list) 
            [x] 
            (ite (lte x (head list)) 
                 (Cons x list) 
                 (Cons (head list) (insert x (tail list))));

msort 
   = !list -> 
        ite (or (null list) (singleton list)) 
            list 
            (merge (msort (topHalf list)) (msort (bottomHalf list)));

topHalf 
   = !list -> take (div (length list) 2) list;

bottomHalf 
   = !list -> drop (div (length list) 2) list;

merge 
   = !list1 -> !list2 -> 
        ite (null list1) 
            list2 
            (ite (null list2) 
                 list1 
                 (ite (lte (head list1) (head list2)) 
                      (Cons (head list1) (merge (tail list1) list2)) 
                      (Cons (head list2) (merge list1 (tail list2)))));

test1 = isort [12,4,18,3,1,2];

test2 = msort [12,4,18,3,1,2];