mergesort

Babel + JSX

function mergerSort(arr) {
    let step = 1,
        len = arr.length;
    // 如果数组为1|0则直接返回
    if (len < 2) return arr;
    let left_start, right_start;
    while (step < len) {
        left_start = 0;
        right_start = step;
        //当数组长度为偶数时,并且小于数组总长度,执行循环
        while (right_start + step <= len) {
            // 分开对数组进行相关排序
            sortArr(arr,left_start,left_start+step,right_start,right_start+step);
            left_start = right_start+step;
            right_start  = left_start+step;
        }
        // 当数组长度为奇数时, 再进行一次排序
        if(right_start < len){
        	sortArr(arr,left_start,left_start+step,right_start,len);
        }
        step *= 2;
    }
    return arr;
}

/**
 * 对指定两个子数组数组进行排序
 */
function sortArr(arr, left_start, left_end, right_start, right_end) {
    // 生成左右两个数组
    let left_len = left_end - left_start,
        right_len = right_end - right_start,
        left_arr = new Array(left_len+1),
        right_arr = new Array(right_len+1);
    // 添加两个数组的数据
    let k = left_start;
    for(var i=0;i<left_len;i++){
    	left_arr[i] = arr[k+i];
    }
    k = right_start;
    for(var i=0;i<right_len;i++){
    	right_arr[i] = arr[k+i];
    }
    // 放入一个无限大的数Infinity 方便下面比较
    left_arr[left_len] = right_arr[right_len] = Infinity;
    // 排序比较两个数组
    // 已知,两个数组都是左边小右边大.
    let left_index = 0,
    right_index = 0;

    for(var i=left_start;i<right_end;i++){
    	if(left_arr[left_index]<=right_arr[right_index]){
    		arr[i] = left_arr[left_index];
    		left_index++;
    	}else{
    		arr[i] = right_arr[right_index];
    		right_index++;
    	}
    }
}

function randomArr() {
    let arr = [];
    for (var i = 0; i < 500; i++) {
        arr.push(i);
    }
    arr.sort(() => Math.random() - 0.5);
    return arr;
}
let arr = randomArr();


console.log(mergerSort(arr));