javascript - 为什么说这是‘原地排序’？
最近看Nicholas大神的JS算法博客（原文地址：Computer science in JavaScript: Merge sort）， 在这里他实现两种归并排序， 第一种是非原地排序，第二种是原地排序。 我觉得这两种方式的空间复杂度都一样，区别只在于其返回值是否原数组，Nicholas说第二种是原地排序， 但我之前看的原地排序的概念不是说跟额外的空间复杂度有关吗？ 而在这篇博客里的原地排序与空间复杂度好像没有关系。那原地排序的概念到底是指什么呢，按照Nicholas的说法是否可以理解为只要是在原数组上处理就是原地排序呢？
这里贴出原文中的代码：
注意：该博客中的例子只为阐述概念，并不强调性能
非原地排序实现归并：
function merge(left, right){
var result = [],
il = 0,
ir = 0;
while (il < left.length && ir < right.length){
if (left[il] < right[ir]){
result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}
return result.concat(left.slice(il)).concat(right.slice(ir));
}原地排序实现归并：
function mergeSort(items){
if (items.length < 2) {
return items;
}
var middle = Math.floor(items.length / 2),
left = items.slice(0, middle),
right = items.slice(middle),
params = merge(mergeSort(left), mergeSort(right));
// Add the arguments to replace everything between 0 and last item in the array
params.unshift(0, items.length);
items.splice.apply(items, params);
return items;
}公共函数merge：
function merge(left, right){
var result = [],
il = 0,
ir = 0;
while (il < left.length && ir < right.length){
if (left[il] < right[ir]){
result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}
return result.concat(left.slice(il)).concat(right.slice(ir));
}
