最近遇到排序算法比较多，首先是快排，V8实现了一份快排，大部分的浏览器也是用快排的，快排是不稳定排序，而且最差的时间复杂度其实是o(n^2),好像归并排序也有被其他浏览器实现。然后上次一个面试官问我基本有序数组用什么排序，我想了一下，其实我可以写个提前终止的冒泡，嘿嘿。

1. 快速排序

快排的基础就是选择一个基准的元素，然后根据这个元素来划分数组，分成大于和小于这个元素的两部分,然后这个元素的位置就是确定的，然后再递归确定大于和小于这个元素的部分。
快排在基本有序的情况下，如果正序交换次数会比较少，但是感觉时间复杂度趋向于0(n^2)。
V8虽然是用快排，但是实现了插入排序，用来处理数组大小小于22的情况，

In-place QuickSort algorithm. For short (length <= 22) arrays, insertion sort is used for efficiency.

阮一峰实现了一份快排的代码，但是个人觉得他没有很好地利用快排空间复杂度的优势，甚至他用数组的函数的时候，其实也要考虑额外的复杂度，所以个人觉得时间复杂度也超了。所以我根据《算法导论》的思路实现了一份JavaScript版本，优点嘛，基本实现了没有额外空间复杂度，除了递归的O(log(n))。

function quick_sort(arr) {
    function swap(i,j) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    function split(start,end) {
        var cmp = arr[end];
        var loc = start;
        for(var i=start;i<end;i++){
            if(arr[i]<cmp){
                swap(loc,i);
                loc++;
            }
        }
        swap(loc, end);
        return loc;
    }
    
    function helper(start,end) {
        if(start<end){  //记得判断end要大于start
            var q = split(start,end);
            helper(start,q-1);
            helper(q+1,end);
        }
    }
    helper(0,arr.length-1);
    return arr;
}

2. 归并排序

归并排序的思想也比较简单，主要是实现二路归并，但是归并算法是无法无视额外的空间复杂度的，也就是二路归并的时候，需要两个子数组，以及一个归并后的数组，他们是无法重合的。
上次面试官让我不用递归和栈来写一份归并，其实就是用for循环模拟，第一次写的时候，空间利用率并不是很高，现在给一份优化的版本，主要是把两个数组归并后生成的新数组去掉，然后用原始数组来存储新数组。

function merge_sort(arr) {
    function merge(arr1,arr2,loc) {
        var n1 = arr1.length;
        var n2 = arr2.length;
        var i=0,j=0;
        arr1.push(Number.POSITIVE_INFINITY);
        arr2.push(Number.POSITIVE_INFINITY);
        while(i+j<n1+n2){
            if(arr1[i]<arr2[j]){
                arr[loc] = arr1[i];
                i++;
            }else{
                arr[loc] = arr2[j];
                j++;
            }
            loc++;
        }
    }

    var nn = arr.length;
    var merge_length = 1;
    while(merge_length<nn) {
        for (var i = 0; i + 2 * merge_length < nn; i = i + 2 * merge_length) {
            merge(arr.slice(i,i+merge_length),arr.slice(i+merge_length,i+2*merge_length),i);
        }
        if(i+merge_length<nn){
            merge(arr.slice(i,i+merge_length),arr.slice(i+merge_length,nn),i);
        }
        merge_length *=2;
    }
    return arr;
}

还有一种是用递归来实现，不过感觉没有严格按照递归的1，2，4这样的顺序进行合并，不过思路是差不离的。

function merge_sort(arr) {
    function merge(arr1,arr2,loc) {
        var n1 = arr1.length;
        var n2 = arr2.length;
        var i=0,j=0;
        arr1.push(Number.POSITIVE_INFINITY);
        arr2.push(Number.POSITIVE_INFINITY);
        while(i+j<n1+n2){
            if(arr1[i]<arr2[j]){
                arr[loc] = arr1[i];
                i++;
            }else{
                arr[loc] = arr2[j];
                j++;
            }
            loc++;
        }
    }
    function helper(start,end) {
        if (start < end) {
            var mid = Math.floor((start + end) / 2);
            helper(start, mid);
            helper(mid + 1, end);
            merge(arr.slice(start, mid + 1), arr.slice(mid + 1, end+1), start);
        }
    }
    helper(0,arr.length-1);
    return arr;
}