排序算法inJavaScript

插入排序：

// javascript部分
Array.prototype.insertSort = function(){
    for(var j = 1;j<this.length;j++){
        const key = this[j];
        var i = j-1
        for (;i>=0&&this[i]>key;i--){
            this[i+1] = this[i];
        }
        this[i+1] = key;
    }
}

// MIT公开课伪代码

for j<- 2 to n step 1
  do key <- A[j]
    i = j-1
    while i>0 AND A[i]>key
      do A[i+1] <- A[i]
  A[i+1]=key

原理：实际上是在原数组的前J位构筑一个新的排序数组，并且将源数组中的每一个值插入这个新数组的适当位置，使新数组是排序的。但是所谓新数组实际还是源数组，没有空间上的额外开销。

归并排序

// 自产自销非递归归并
Array.prototype.mergeSort = function(){
    var mergeArray = function(arr1,arr2){
        var result = [];
        while(arr1.length*arr2.length>0){
            if (arr1[0] > arr2[0]){
                result.push(arr2.shift());
            }else {
                result.push(arr1.shift());
            }
        }
        while(arr1.length>0){
            result.push(arr1.shift());
        }
        while(arr2.length>0){
            result.push(arr2.shift());
        }
        return result;
    }
    var deepCopy = function(arr){
        var tmp = [];
        for(let i = 0;i<arr.length;i++){
            tmp.push(arr[i]);
        }
        return tmp;
    }
    var mergeList = [];
    for(let i = 0;i<this.length;i++){
        var temp = [];
        temp.push(this[i])
        mergeList.push(temp);
    }
    while(mergeList.length>1){
        var tempList = deepCopy(mergeList);
        mergeList.length = 0;
        for(let i = 0; i<Math.floor(tempList.length/2)+tempList.length%2;i++){
            mergeList.push(mergeArray(tempList[i],tempList[tempList.length-1-i]));
        }
    }
    return mergeList[0];
}
// 因为用了DeepCopy实际上，时间复杂度会多加一层，不过不deepCopy的话内存指向有很大的问题。

// 递归实现

对于归并的时间复杂度，详情可以看MIT的算法导论，答案是n*log2(n)。
我在想计算一个数能被2除几次的时候第一时间想到的是开根号，并且一瞬间忘了对数是求幂的逆运算，对不起我的数学老师们。
第一节课讲完了，他没讲归并怎么实现……
等我看完下节课更一下。