/**
* @param {number[]} nums
* @return {number[]}
*/
function merge_sort(left, right) {
console.log("eft, right: ", 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;
}
var sortArray = function (nums) {
console.log("nums: ", nums);
if (nums.length < 2) return nums;
let mid = Math.floor(nums.length / 2);
let left = nums.slice(0, mid);
let right = nums.slice(mid, nums.length);
return merge_sort(sortArray(left), sortArray(right));
};
// sortArray([5, 2, 3, 1]);
// sortArray([5, 1, 1, 2, 0, 0]);
// console.log("sortArray([5, 1, 1, 2, 0, 0]);: ", sortArray([5, 1, 1, 2, 0, 0]));
// console.trace("sortArray([5, 2, 3, 1]);: ", sortArray([5, 2, 3, 1]));
재귀함수에서 call Stack 작업상황이 너무 헷걸려 트리로 도식화 해 보았다.
merge_sort
자체를 리턴한다는 것에 유의하자
복기
배열.shift()
맨 앞에 것들을 제거한 요소를 리턴한다.