// quick sort
function qsort(arr) {
    if (arr.length === 0) return []
    const [pivot, ...tail] = arr
    const [smaller, bigger] = partition(tail, x => x < pivot)
    return [...qsort(smaller), pivot, ...qsort(bigger)]
    
    // helper function
    function partition(arr, f, a=[], b=[]) {
        if (arr.length === 0) return [a, b]
        const [head, ...tail] = arr
        return f(head) 
            ? partition(tail, f, [...a, head], [...b])
            : partition(tail, f, [...a], [...b, head])
    }
}

// insertion sort
function isort(arr) {
    if (arr.length === 0) return []
    const [head, ...tail] = arr
    return insert(head, isort(tail))
    
    // helper function
    function insert(x, arr) {
        if (arr.length === 0) return [x]
        const [head, ...tail] = arr
        return (x < head)
            ? [x, ...insert(head, tail)]
            : [head, ...insert(x, tail)]
    }
}

// merge sort
function msort(arr) {
    if (arr.length <= 1) return arr
    const [head, ...tail] = arr
    const [left, right] = halve(arr)
    return merge(msort(left), msort(right))
    
    // helper function
    function halve(arr) {
        const mid = Math.ceil(arr.length / 2)
        const left = arr.slice(0, mid)
        const right = arr.slice(mid)
        return [left, right]
    }
    
    // helper function
    function merge(left, right) {
        if (right.length === 0) return left
        if (left.length === 0) return right
        const [x, ...xs] = left
        const [y, ...ys] = right
        return (x < y)
            ? [x, ...merge(xs, right)]
            : [y, ...merge(left, ys)]
    }
}

// driver code
const unsorted = [4,2,5,3,1]
console.log("input: ", unsorted)
console.log("qsort: ", qsort(unsorted));
console.log("isort: ", qsort(unsorted));
console.log("msort: ", qsort(unsorted));