병합정렬은 한 배열을 반복적으로 반으로 나누어 정렬하고 다시 합치는 방식으로 이루어지는 정렬 알고리즘이다. 병합정렬은 보통 두 가지 함수로 이루어져 있는데
해당 함수는 다음과 같다.
1. 이미 나누어 정렬한 배열을 하나로 합치는 함수
function merge(left, right){ const result = []; while(left.length > 0 && right.length > 0){ if(left[0] <= right[0]) { result.push(left.shift()); } else if(left[0] > right[0]) { result.push(right.shift()); } } return [...result, ...left, ... right]; }
해당 함수는 반으로 나누어 전달받은 인자를 비교해서 정렬하게 된다.
2. 배열을 반으로 나누어, merge 함수에게 left, right 인자를 넘겨주는 함수
function mergeSort(arr) { if(arr.length === 1) return arr; const middleIdx = Math.floor(arr.length / 2); const left = arr.slice(0, middleIdx); const right = arr.slice(middleIdx); return merge(mergeSort(left), mergeSort(right));
해당 함수는 배열의 길이가 1이 될때까지(요소가 1개만 남을 때까지)재귀적 반복과정을 거쳐서 merge함수에 left와 right로 전달되게 된다. 이후 왼쪽 배열과 오른쪽 배열을 비교해서 합치는 과정을 반복하게 되고 결과적으로는, 정렬된 배열을 만들 수 있다.