시간 복잡도: O(NlogN)
function mergeSort(arr) {
// 배열의 길이가 1 이하이면 그대로 반환
if (arr.length <= 1) {
return arr;
}
// 배열을 반으로 나누기 위한 인덱스 계산
const midIndex = Math.floor(arr.length / 2);
// 배열을 반으로 나누기
const leftArr = arr.slice(0, midIndex);
const rightArr = arr.slice(midIndex);
// 분할된 배열을 각각 재귀적으로 정렬
const sortedLeftArr = mergeSort(leftArr);
const sortedRightArr = mergeSort(rightArr);
// 정렬된 배열을 병합
return merge(sortedLeftArr, sortedRightArr);
}
function merge(leftArr, rightArr) {
const result = [];
// 두 배열 중 하나가 빌 때까지 반복
while (leftArr.length && rightArr.length) {
// 두 배열의 첫 번째 요소를 비교하여 작은 것을 결과 배열에 추가
if (leftArr[0] < rightArr[0]) {
result.push(leftArr.shift());
} else {
result.push(rightArr.shift());
}
}
// 남은 요소를 결과 배열에 추가
return [...result, ...leftArr, ...rightArr];
}