A Variety-Sort in ES6

variety-sort.js

function varietySort(array) {
    // 1. Cut the list in half
    const [ left, right ] = varietySort.split(array);
    varietySort.rejoin(
        array,
        varietySort.left(left),
        varietySort.right(right)
    );
    return array;
}

varietySort.split = function(array) {
    const left = array.splice(0, array.length / 2);
    const right = array.splice(0);
    return [ left, right ];
}

varietySort.rejoin = function(array, left, right) {
    while(left.length && right.length) {
        if (left[0] < right[0]) {
            array.push(left.shift());
        } else if (right[0] < left[0]) {
            array.push(right.shift());
        }
    }
    if (left.length) {
        [].push.apply(array, left);
    }
    if (right.length) {
        [].push.apply(array, right);
    }
    return array;
}

// Bubble-sort until the right-half of this array is sorted
varietySort.left = function(array) {
    for (let j = array.length; j > (array.length / 2) + 1; --j) {
        for (let i = 1; i < array.length; ++i) {
            if (array[i] < array[i - 1]) {
                [ array[i], array[i - 1] ] = [ array[i - 1], array[i] ];
            }
        }
    }

    const [ left, right ] = varietySort.split(array);

    return varietySort.rejoin(
        array,
        varietySort.left.left(left),
        varietySort.left.right(right),
    );
};

varietySort.left.left = function(array) {
    const from = array.splice(0, array.length);
    for (let i = 0; i < from.length; ++i) {
        let j = 0;
        while (j < array.length && from[i] > array[j]) {
            j++;
        }
        array.splice(j, 0, from[i]);
    }
    return array;
}

varietySort.left.right = function(array) {
    return array;
}

// Cut this half in half
varietySort.right = function(array) {
    const [ left, right ] = varietySort.split(array);
    return varietySort.rejoin(
        array,
        varietySort.right.left(left),
        varietySort.right.right(right),
    );
}

varietySort.right.left = function(array) {
    const shuffle = () => {
        for (let i = array.length - 1; i > 0; --i) {
            const j = Math.floor(Math.random() * (i + 1));
            [ array[i], array[j] ] = [ array[j], array[i] ];
        }
    };
    for (let i = 1; i < array.length; ++i) {
        if (array[i] < array[i - 1]) {
            i = 0;
            shuffle();
        }
    }

    return array;
}

varietySort.right.right = function quickSort(array, low = 0, high = array.length - 1) {
    const partition = (low, high) => {
        let pivot = array[high];
        let i = low - 1;
        for (let j = low; j <= high - 1; ++j) {
            if (array[j] <= pivot) {
                ++i;
                [ array[j], array[i] ] = [ array[i], array[j] ];
            }
        }
        [ array[i + 1], array[high] ] = [ array[high], array[i + 1] ];
        return i + 1;
    };
    if (low < high) {
        const pi = partition(low, high);
        quickSort(array, low, pi - 1);
        quickSort(array, pi, high);
    }
    return array;
}

const array = [1, 10, 12, 3, 8, 11, 4, 9, 13, 16, 6, 2, 7, 15, 14, 5];

console.log(array);
console.log(varietySort(array));