排序算法——归并排序

归并排序是分治算法的一种，它的思想比较多个小的有序集合，然后合并成一些集合，然后再两两合并合并成一些大的集合，最终合并成一个集合，这个大集合就是最终的结果了。

归并排序分为两大类，分为自底向上的归并排序，和自顶向下的两大类，自顶向下的算法一般我们用递归算法来实现，自底向上的算法我们一般通过，where循环来实现。
归并排序的时间复杂度是O(n*logn)，当然归并算法也有很多可以优化的地方，例如我们已经有序的两个数组，并且可以直接连接起来的话，就不需要merage了，还有就是当归并排序后期，我们的数组已经可以称为局部有序了，我们可以在后期调用插入排序，这样虽然不能在时间复杂度级别上优化我们的算法，但是也可以优化很多的。

自顶向下的算法：

/**
 * Created by linSir on 17/2/9.
 */
function merge(data, left, center, right) {
    var tmpArr = new Array();
    var mid = center + 1;
    var third = left;
    var tmp = left;
    while (left <= center && mid <= right) {
        if (data[left] <= data[mid]) {
            tmpArr[third++] = data[left++];
        } else {
            tmpArr[third++] = data[mid++];
        }
    }
    while (mid <= right) {
        tmpArr[third++] = data[mid++];
    }
    while (left <= center) {
        tmpArr[third++] = data[left++];
    }
    while (tmp <= right) {
        data[tmp] = tmpArr[tmp++];
    }
    console.log(data);
    console.log(tmpArr);
    return data;
}

function sort(data, left, right) {
    if (left >= right)
        return;
    var center = parseInt((left + right) / 2);
    sort(data, left, center);
    sort(data, center + 1, right);
    merge(data, left, center, right);
}
var data = [1, 1000, 4, 40, 2, 5, 100, 88];
sort(data, 0, data.length - 1);

结果：

Paste_Image.png

//TODO