- //归并排序
- Array.prototype.mergeSort = function(s, e, b) {
- if (s == null)
- s = 0;
- if (e == null)
- e = this.length - 1;
- if (b == null)
- b = new Array(this.length);
- if (s >= e)
- return;
- var m = (s + e) >> 1;
- this.mergeSort(s, m, b);
- this.mergeSort(m + 1, e, b);
- for (var i = s, j = s, k = m + 1; i <= e; ++i)
- b[i] = this[(k > e || j <= m && this[j] < this[k]) ? j++ : k++];
- for (var i = s; i <= e; ++i)
- this[i] = b[i];
- }
算法性能：可以选取“归并操作”作为基本操作，“归并操作”即为将待归并表中元素复制到一个存储归并结果的表中的过程，其次数为要归并的两个子序列中元素个数之和。算法总共需要进行logn趟排序，每趟排序执行n次基本操作，因此整个归并排序中总的基本操作执行次数为nlogn，即时间复杂度为O(nlogn)，说明归并排序时间复杂度和初始序列无关。由于归并排序需要转存整个待排序列，因此空间复杂度为O(n)。
一些结论
（1）快速排序、希尔排序、归并排序、堆排序的平均时间为O(nlogn)，其他的为O(n*n)。
（2）快速排序、希尔排序、选择排序、堆排序不稳定，其他的稳定。
（3）经过一趟排序能够保证一个元素到达最终位置的是冒泡排序、快速排序、选择排序、堆排序。
（4）元素比较次数和原始序列无关的是选择排序、折半插入排序。
（5）排序趟数和原始序列有关的是交换类排序。
（6）直接插入排序和折半插入排序的区别是寻找插入位置的方式不同，一个是按顺序查找方式，另一个是按折半查找方式。