class sort {
constructor() {
}
/**
* 归并排序 时间复杂度O(nlogn) 空间复杂度O(n)
*
* @param {any} arr
* @returns
*
* @memberof sort
*/
sort6(arr) {
if(arr.length < 2) {
return arr;
}
let len = arr.length;
let middleVal = Math.floor(len / 2);
let left = arr.slice(0, middleVal);
let right = arr.slice(middleVal, len);
return this.merge(this.sort6(left), this.sort6(right));
}
/**
* 归并排序划分后进行的分割函数
*
* @param {any} left
* @param {any} right
* @returns
*
* @memberof sort
*/
merge(left, right) {
let result = [];
while(left.length && right.length) {
if(left[0] < right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length) {
result.push(left.shift());
}
while(right.length) {
result.push(right.shift());
}
return result;
}
}
