20thSept_Sorting2

// approach B
// n/2

// split the list in half
// sort each half using wishful thinking
// merge the sorted lists together

// wishful thinking
// considering xs and ys are already sorted

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

// put the first n elements of xs into a list
function take(xs, n) {
    return n===0
        ? null 
        : append(list(head(xs)), take(tail(xs), n-1));
}

// drop the first n elements from the list and return the rest
function drop(xs, n) {
    
    // return filter(x => is_null(member(x, take(xs,n))), xs);
    // above is WRONG cause removes repeated elements from the whole list
    
    /*
    const len = length(xs);
        
    function helper(n){
            
        return n === 0
            ? null 
            : append(list(list_ref(xs, len - n)), helper(n-1));
            
        
        
    }
    
    return helper(len - n);
    */
    
    function helper(xs, counter, n){
        
        return counter <= n ? helper(tail(xs), counter + 1, n) : xs;
        
    }
    
    return helper(xs, 1, n);
    
}

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

function merge_sort(xs) {
    if (is_null(xs) || is_null(tail(xs))) {
        return xs;
    } else {
        const mid = middle(length(xs));
        return merge(merge_sort(take(xs, mid)),
        merge_sort(drop(xs, mid)));
    }
}

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