정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.
number 타입을 요소로 갖는 배열
arr[i]는 정수
arr.length 100,000 이하
number 타입을 요소로 갖는 배열을 리턴해야 합니다.
배열의 요소는 오름차순으로 정렬되어야 합니다.
arr[i] <= arr[j] (i < j)
병합 정렬을 구현해야 합니다.
arr.sort 사용은 금지됩니다.
입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.
let output = mergeSort([3, 1, 21]);
console.log(output); // --> [1, 3, 21]
병합 정렬은 표준 라이브러리에서 정렬을 구현할 때 퀵 정렬이나 힙 정렬의 대안으로 사용하는 최적화된 정렬 알고리즘입니다. 병합 정렬은 다음과 같은 알고리즘을 사용합니다.
반복적 접근
1. 주어진 배열이 "정렬된" 부분 리스트로 나뉘어집니다. [4,7,4,3,9,1,2] -> [[4],[7],[4],[3],[9],[1],[2]] // 2. 인접한 부분 리스트 2개가 정렬된 부분 리스트로 병합됩니다. [[4],[7],[4],[3],[9],[1],[2]] -> [[4,7],[3,4],[1,9],[2]] // 2. 병합 과정 (반복) : [[4,7],[3,4],[1,9],[2]] -> [[3,4,4,7], [1,2,9]] // 2. 병합 과정 (반복) : [[3,4,4,7], [1,2,9]] -> [[1,2,3,4,4,7,9]] // 3. 마무리 : 정렬된 배열이 리턴됩니다. [1,2,3,4,4,7,9]
재귀적 접근
주어진 배열을 절반으로 나눕니다. 4, 7, 4, 3, 9, 1, 2 -> 4, 7, 4, 3, 9, 1, 2 // 두 배열이 재귀적으로 정렬됩니다. 4, 7, 4 -> 4, 4, 7 -> 1, 2, 3, 9 // 두 배열이 병합됩니다. 4, 7, 4, 3, 9, 1, 2 -> 1, 2, 3, 4, 4, 7, 9 // 2단계에서 나뉘어진 각각의 배열 4, 7, 4에 대해서도 1-3번의 과정이 재귀적으로 똑같이 진행됩니다. // 주어진 배열을 절반으로 나눕니다. 4, 7, 4 -> 4, 7, 4 // 두 배열이 재귀적으로 정렬됩니다. 4 -> 4 -> 4, 7 // 두 배열이 병합됩니다. 4, 4, 7 -> 4, 4, 7 // 이 과정의 2단계에서 나뉘어진 4, 7에 대해서도 재귀가 호출됩니다. 4는 원소가 하나이기 때문에 정렬하지 않아도 되겠죠? // 주어진 배열을 절반으로 나눕니다. 7, 4 -> 7, 4 // 두 배열이 재귀적으로 정렬됩니다. 7 -> 7 -> 4 // 두 배열이 병합됩니다. 7, 4 -> 4, 7 // 모든 재귀 호출이 완료되면 3단계에서 병합이 되기 때문에 최종적으로 정렬된 하나의 배열이 리턴됩니다.
function merge(left, right) {
const sortedArr = [];
while (left.length && right.length) { // left 나 right 둘 중 하나라도 빈배열이면 while문을 빠져나온다
if (left[0] <= right[0]) { // left와 right의 0번째 인덱스 중 작은 요소를 sortedArr에 집어 넣는다. 같을 경우 뭘 집어넣든 상관없다
sortedArr.push(left.shift());
} else {
sortedArr.push(right.shift());
}
}
return [...sortedArr, ...left, ...right];
}
function mergeSort(arr) {
if (arr.length === 1) return arr;
const middle = Math.ceil(arr.length / 2);
const left = arr.slice(0, middle);
const right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
아직은 내 스스로의 힘으로 함수 2개를 이용한 알고리즘 코드를 풀기엔 아직 부족한 점이 많다
일단 어떤 로직으로 흘러가는지 정확히 이해하고,
한번 배운 것을 놓치지 않도록 제대로 숙지하자!