병합 정렬(합병 정렬)은 데이터들을 잘게 쪼갠 다음에 하나로 합치는 과정에서 정렬하는 알고리즘이다.
- 시간 복잡도는 O(n logn)이고, 재귀 함수를 이용해서 만든다.
병합 정렬 예시 사진)
- 병합 정렬은 위의 그림처럼 데이터를 절반씩 쪼개는 divide 작업을 먼저 하는데 이 작업은 데이터가 하나만 남을 때까지 반복한다. 그 후에 하나씩 쪼개진 데이터를 정렬을 하면서 다시 그룹화한다.
병합 정렬은 일반적으로 다음과 같은 세 단계로 나뉜다.
- 분할(Divide): 입력 리스트를 같은 크기의 두 개의 부분 리스트로 분할합니다. 이때 분할은 리스트의 중간 지점에서 수행된다.
- 정복(Conquer): 각 부분 리스트를 재귀적으로 병합정렬을 이용해 정렬한다. 이 과정은 입력 리스트의 크기가 충분히 작아질 때까지 반복된다.
- 병합(Merge): 정렬된 두 부분 리스트를 하나의 정렬된 리스트로 병합한다.
위를 함수로 표현하면 Merge Sort는 배열을 쪼개는 단계와 병합하는 단계로 나눠진다.
function mergeSort(arr): 배열을 반으로 쪼개서 merge 함수에게 left, right 인자를 넘겨주는 함수function merge(left, right): 이미 소팅된 배열 left, right 받아서 하나로 합치는 순수한 함수- merge함수는 순수한 함수이고, mergeSort는 재귀로 함수를 사용한다.
merge 함수는 이미 정렬 된 left(배열), right(배열)를 인자로 받아서 하나로 합치는 기능
function merge(left, right) {
const resultArray = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
resultArray.push(left[leftIndex]);
leftIndex++;
} else {
resultArray.push(right[rightIndex]);
rightIndex++;
}
}
return resultArray.concat(left.slice(leftIndex), right.slice(rightIndex));
}
// 1. left와 right으로 나눠진 배열은 각각 merge라는 함수를 호출하여 병합한다.
// 2. merge함수는 최종으로 합쳐진 배열을 담을 resultArray라는 배열을 준비하고
// 두 배열의 앞자리 숫자부터 비교하여 배열에 담는다.
// 3. while문을 빠져나오면 두 배열 중 숫자가 작은 한 쪽 배열의 요소가 resultArray에 담기기 때문에
// resultArray에 left와 right 배열을 다시 합치고 리턴한다.mergeSort 는 반으로 쪼개서 merge 에게 인자를 넘겨주는 기능
function mergeSort(array) {
if (array.length < 2) {
return array;
}
const mid = Math.floor(array.length / 2);
const left = array.slice(0, mid);
const right = array.slice(mid);
return merge(mergeSort(left), mergeSort(right));
....
}
// array의 길이가 2보다 작으면 분할이 끝난 것이여서 return함
// array의 길이가 2보다 크다면 반으로 나눈다.function mergeSort(array) {
if (array.length < 2) {
return array;
}
const mid = Math.floor(array.length / 2);
const left = array.slice(0, mid);
const right = array.slice(mid);
return merge(mergeSort(left), mergeSort(right));
function merge(left, right) {
const resultArray = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
resultArray.push(left[leftIndex]);
leftIndex++;
} else {
resultArray.push(right[rightIndex]);
rightIndex++;
}
}
return resultArray.concat(left.slice(leftIndex), right.slice(rightIndex));
}
}
console.log(mergeSort([5, 4, 3, 2, 1])); // (5) [1, 2, 3, 4, 5]
위는 실행결과를 순서대로 표기한 것이다.