1. 소개
병합정렬은 대표적은 분할정복 알고리즘 중 하나로, 리스트를 반으로 나눈 뒤 각각을 재귀적으로 정렬하고, 정렬된 두 리스트를 합쳐 하나의 리스트를 만드는 알고리즘 이다.
2. 작동개념
일반적으로 세 단계로 구성된다.
- 분할: 입력리스트를 같은 크기의 두개의 부분 리스트로 분할한다. 이때 분할은 리스트의 중간 지점에서 수행된다.
- 정복: 각 부분 리스트를 재귀적으로 병합정렬을 이용해 정렬한다. 이 과정은 입력 리스트의 크기가 충분히 작아질 때까지 반복된다.
- 병합: 정렬된 두 부분 리스트를 하나의 정렬된 리스트로 병합한다.
3. 시간 복잡도
O(n log n)
계속 나누고 나눈 다음 합치고 또 합칠 뿐이기 때문에 병합 정렬은 예외 케이스가 없다.(안정성)
4. 구현
2가지 함수를 이용해 구현할 수 있다.
- mergeSort(arr) : 반으로 나누어 주는 함수
- merge(left,right) : 반으로 나누어 준 함수를 갖고 정렬해 새로운 배열로 만들어주는 함수
(이 과정에서 새로운 배열로 만들어 주기 때문에 메모리가 필요하다.)
function merge(left, right) {
const sortedArr = [];
while (left.length && right.length) {
//left[0]이 더작을 경우 같을때는 누가 먼저 들어가도 상관X
if (left[0] <= right[0]) {
sortedArr.push(left.shift());
} else {
sortedArr.push(right.shift());
}
}
//left,right 둘 중 하나는 요소가 남아있기 때문에 sortedArr 뒤에 붙여서 출력
//비어있으면 spread Syntax에도 아무것도 없기 때문에 그냥 다 붙여준다.
return [...sortedArr, ...left, ...right];
}
function mergeSort(arr) {
if (arr.length === 1) return arr;
const boundary = Math.ceil(arr.length / 2);
//slice로 해주기 때문에 원본 arr은 손상 없다.
const left = arr.slice(0, boundary);
const right = arr.slice(boundary);
//요소가 1개 일 때까지 재귀를 실행해 요소가 1개일 때 두 left,right부터
//차근차근 merge(정렬해서 합치기)해주면 된다.
return merge(mergeSort(left), mergeSort(right));
}
const arr = [7, 4, 3, 2, 1, 6, 5];
const sortedArray = mergeSort(arr);
console.log(arr); //[7, 4, 3, 2, 1, 6, 5]
console.log(sortedArray); //[1, 2, 3, 4,5, 6, 7]