말그래도 배열을 병합(merge)하여 정렬하는 알고리즘이다. 병합이라는 말과 같이 배열을 재귀적으로 쪼갤 수 없는 단위 즉, 요소가 1개가 남을 때까지 쪼갠 후 정렬하고 쪼개진 요소들을 병합한다.
출처: 위키백과 - Swfung8 자작
병합정렬을 위해선 두가지의 함수가 필요하다.
// 입력받은 배열을 합칠 result 배열 선언
// 입력받은 배열1, 배열2의 요소가 없을 때까지
// 배열1과 배열2의 첫번째요소 중 작은 녀석들을 result에 담아준다.
// result와 배열1, 배열2의 남은 요소들을 배열로 다시 묶어 리턴한다.
// 재귀적 호출 시 종료 조건으로 입력 받은 배열의 길이가 1개일 경우 즉, 이미 정렬된 경우 해당 배열을 리턴한다.
// 입력받은 배열을 두개로 쪼갠다.
// 쪼개기 위해 mid변수를 선언하고 입력받은 배열의 길이 / 2 값을 내림하여 담아둔다.
// 쪼갠 뒤 왼쪽 배열을 담을 left 배열을 선언하고 담는다.
// 오른쪽 배열 역시 담아둔다.
// 재귀함수를 콜하여 left배열과 right배열을 담아 merge함수의 인자로 넣어준 뒤, 그 값을 리턴한다.
const merge = (left, right) => {
const result = [];
while(left.length !== 0 && right.length !== 0) {
left[0] <= right[0] ? result.push(left[0]) : result.push(right[0]);
}
return [...result, ...left, ...right];
}
const mergeSort = (arr) => {
// 재귀 종료 조건
if(arr.length < 2) return arr;
const midIdx = Math.floor(arr.length / 2);
const leftArr = arr.slice(0, midIdx);
const rightArr = arr.slice(midIdx);
return merge(mergeSort(left), mergeSort(right));
}