# Slow versions of insertion sort and merge sort.
#
# They are slow because they do not use strictness annotations.
# Lazy term reduction causes much duplicated work.
#
# Compare this with SortStrict.bs
#
# Author: Bernie Pope
# Date:   10 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];