Merge Sort

//Aim is to divide the list recursively into smaller sublists
//until each sublist conatins only 1 element or no elements
function merge_sort(xs) {
    if (is_null(xs) || is_null(tail(xs))){
        return xs;
    } else {
        const mid = middle(length(xs)); // to find value of half
        return merge (merge_sort(take(xs,mid)), merge_sort(drop(xs, mid)));
    }
}

//Aim is to combine two sorted sublists into a single sorted sublist
function merge(xs,ys){
    if (is_null(xs)) {
        return ys;
    } else if (is_null(ys)) {
        return xs;
    } else {
        const x = head(xs);
        const y = head(ys);
        return x < y
               ? pair(x, merge(tail(xs), ys))
               : pair(y, merge(xs, tail(ys)));
    }
}

//Half rounded downwards
function middle(n){
    return math_floor(n/2);
}

//Take first n elements of list
function take(xs,n){
    return n===0
           ? null 
           : pair(head(xs), take(tail(xs), n-1));
}
//Drop first n elements of list, return the rest         
function drop(xs, n){
    return n === 0
           ? xs
           : drop(tail(xs), n-1);
}


// Test
merge_sort(list(7, 6, 3, 8, 4, 6, 5, 9, 8, 3, 1, 5, 2));