병합 정렬(Merge Sort)이란?
병합 정렬은 분할 정복(Divide and Conquer) 방식의 대표적인 정렬 알고리즘입니다. 입력으로 받은 배열의 요소들을 오름차순(작은 값부터 큰 값 순서)으로 정렬하는 것이 목표입니다.
병합 정렬은 배열을 계속 반으로 나눈 뒤, 다시 하나씩 합치면서 정렬하는 방식으로 동작하기 때문에 데이터가 많아도 안정적으로 좋은 성능(O(n log n))을 보여줍니다.
병합 정렬의 동작 단계
- 분할(Divide): 배열을 두 개의 하위 배열로 나누고, 각 하위 배열을 다시 두 개씩 나누는 과정을 반복하여 결국 요소가 하나뿐인 배열들만 남깁니다. 예를 들어 [4,7,5,9,1,3,8,2]라는 배열은 [4], [7], [5], [9], [1], [3], [8], [2]로 분할됩니다.
- 정렬하며 병합(Conquer): 인접한 두 배열씩 비교하고 합칩니다. 예를 들어 [4]와 [7]을 비교·병합해 [4,7]을 만들고, [5]와 [9]를 병합해 [5,9]를 만드는 식으로 진행되어 [4,7], [5,9], [1,3], [2,8] 네 개의 정렬된 배열이 만들어집니다.
- 반복 병합: 같은 방식으로 두 배열씩 다시 비교·병합합니다. [4,7]과 [5,9]를 병합하면 [4,5,7,9]가 되고, 나머지 두 배열도 병합하여 [1,2,3,8]이 됩니다.
- 최종 병합: 마지막으로 남은 두 배열 [4,5,7,9]와 [1,2,3,8]을 병합하면 최종 정렬된 배열 [1,2,3,4,5,7,8,9]가 완성됩니다.
JavaScript 구현 예제
<html>
<body>
<script>
function mSort (array) {
if (array.length === 1) {
return array; // 요소가 하나뿐인 배열이 되면 반환
}
const middle = Math.floor(array.length / 2); // 중간 지점(내림)
const left = array.slice(0, middle); // 왼쪽 절반
const right = array.slice(middle); // 오른쪽 절반
return merge(
mSort(left),
mSort(right)
);
}
// 두 배열을 요소별로 비교하여 정렬된 결과를 반환
function merge (left, right) {
let result = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
const list = [4,7,5,9,1,3,8,2];
document.write(mSort(list));
</script>
</body>
</html>실행 결과
1,2,3,4,5,7,8,9
코드 설명
mSort함수는 재귀적으로 호출되며, 배열 길이가 1이면 더 이상 분할할 수 없으므로 그대로 반환합니다.Math.floor(array.length / 2)로 중간 지점을 구해slice메서드로 왼쪽과 오른쪽 배열로 나눕니다.merge함수는 두 배열의 앞에서부터 요소를 하나씩 비교하여 작은 값을 결과 배열에 추가합니다.- while 루프가 끝난 후
concat으로 남은 요소들을 이어 붙여 최종 정렬된 배열을 완성합니다.