SOURCE

let arr = [9, 0, -1, 0, 4, 3, 2, 99, 40, 24];

// 
function bunbleSort(nums) {
    for(let i = 0; i < nums.length - 1; i++) {
        for(let j = 0; j < nums.length - i - 1; j++) {
            if(nums[j] > nums[j+1]) {
                [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
            }
        }
    }
    return nums;
}

function insertSort(nums) {
    for(let i = 1; i < nums.length; i++) {
        for(let j = i; j > 0; j--) {
            if(nums[j] < nums[j-1]) {
                [nums[j], nums[j - 1]] = [nums[j - 1], nums[j]];
            }
        }
    }
    return nums
}

function selectSort(nums) {
    for(let i = 0; i < nums.length - 1; i++) {
        let minIndex = i;
        for(let j = i + 1; j < nums.length; j++) {
            if(nums[j] < nums[minIndex]) {
                minIndex = j;
            }
        }
        (minIndex !== i) && ([nums[i], nums[minIndex]] = [nums[minIndex], nums[i]]);
    }
    return nums;
}

function quickSort(nums) {
    if(nums.length < 2) {
        return nums;
    }
    let left = [], right = [];
    let mid = Math.floor(nums.length / 2);
    let midValue = nums[mid];
    for(let i = 0; i < nums.length; i++) {
        if(i != mid) {
            nums[i] <= midValue ? left.push(nums[i]) : right.push(nums[i]);
        }
    }
    return [...quickSort(left), midValue, ...quickSort(right)];
}

function mergeSort(nums) {
    if(nums.length < 2) {
        return nums;
    }
    let mid = Math.floor(nums.length / 2);
    let left = nums.slice(0, mid);
    let right = nums.slice(mid);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(nums1, nums2) {
    let nums = [];
    while(nums1.length && nums2.length) {
        nums2[0] > nums1[0] ? nums.push(nums1.shift()) : nums.push(nums2.shift());
    }
    return nums.concat(nums1, nums2);
}


// console.log('冒泡', bunbleSort(arr));
// console.log('插入', insertSort(arr));
// console.log('选择', selectSort(arr));
// console.log('快速排序', quickSort(arr));
console.log('归并排序', mergeSort(arr));