/**
 * @description 归并排序
 */


const input = [5, 4, 3, 2, 1];

const mergeSort = (left, right) => {
    const result = [];
    let leftPoint = 0;
    let rightPoint = 0;
    while(leftPoint < left.length && rightPoint < right.length) {
        if (left[leftPoint] < right[rightPoint]) {
            result.push(left[leftPoint]);
            leftPoint++;
        } else {
            result.push(right[rightPoint]);
            rightPoint++;
        }
    }
    while(leftPoint < left.length) {
        result.push(left[leftPoint]);
        leftPoint++;
    }
    while(rightPoint < right.length) {
        result.push(right[rightPoint]);
        rightPoint++;
    }
    return result;
};

const algorithm = (input) => {
    if (input.length <= 1) {
        return input;
    }
    const mid = Math.floor(input.length / 2);
    const left = input.slice(0, mid);
    const right = input.slice(mid);
    return mergeSort(algorithm(left), algorithm(right));
};
console.log('input', input);
console.log('output', algorithm(input));