{----------------------------------------- merge-sort.mta

                   MERGE SORT

--------------------------------------------------------}

def [sort-by fn seq] [
    ; Sort seq in order of fn.
    if (< (len seq) 2) [return seq]
    set n (floor (len seq) 2)
    return (merge-lists-by fn (sort-by fn (take seq n))
                              (sort-by fn (drop seq n)))
]

def [merge-lists-by fn a b] [
    ; Merge two sorted lists in order of fn.
    if (empty? a) [return b]
    if (empty? b) [return a]
    if (fn (first a) (first b)) [
       return (push (first a)
                    (merge-lists-by fn (rest a) b))
    ]
    else [
       return (push (first b)
                    (merge-lists-by fn a (rest b)))
    ]
]

; Sort a list of numbers.
set L [2 -4 -17 4 5 6 2 35 5 6 1000 7 20 5 19 -3 3]
(? (sort-by < L))

; [-17 -4 -3 2 2 3 4 5 5 5 6 6 7 19 20 35 1000]