SOURCE

//快排，取中间索引，遍历所有数据，比中间值小的放左边，大的放右边，递归比较
let a = [9,8,6,4,6,2]
function quickSort(arr){
    if(arr.length <= 1){
        return arr
    }
    let centerIndex = Math.floor(arr.length/2)    
    let center = arr.splice(centerIndex,1)[0]
	let left = [],
        right=[]
    for(let i =0 ; i< arr.length; i++){
        if(arr[i]<center){
            left.push(arr[i])
        }else{
            right.push(arr[i])
        }
    }
    return quickSort(left).concat(center,quickSort(right))
}
console.log(quickSort(a))


//归并  平分数组 一直到最后的数组为2个元素 然后开始排序合并
let b = [9,8,6,4,6,2]
console.log(mergeSort(b))
function mergeSort(arr){
    if(arr.length<=1)return arr
    let mid = Math.floor(arr.length/2)
    let left = arr.slice(0,mid)   
    let right = arr.slice(mid)
	
    return merge(mergeSort(left),mergeSort(right))

}

function merge(left,right){
    let a = left.length
    let b = right.length
    let arr = []
    let i=0,j=0
    while(i<a && j<b){
        if(left[i]<right[j]){
            arr.push(left[i++])
        }else{
            arr.push(right[j++])
        }
    }
	while(i<a){
        arr.push(left[i++])
    }
    while(j<b){
        arr.push(right[j++])
    }
    return arr

}