쪼개고 합치면 빨라진다
크리스는 이제 자신감이 붙었다. 삽입 정렬로 데이터를 꽤 효율적으로 처리하고 있었기 때문이다.
그러던 어느 날, 회사에서 "10만 건의 사용자 로그"를 날짜별로 정렬해달라는 요청이 왔다.
크리스는 당당하게 삽입 정렬을 돌렸다.
...1초, 2초, 10초...
브라우저는 또다시 멈췄다.
"아니, 삽입 정렬은 빠르다면서요?"
"그건 데이터가 거의 정렬되어 있을 때 얘기지! 무작위 데이터 10만 개를 O(N^2)으로 돌리면 100억 번 연산해야 한다고!"
이제 우리는 '동네 축구' 수준의 정렬에서 벗어나, 프로 리그로 진입해야 한다.
데이터가 아무리 많아도, 아무리 섞여 있어도 흔들리지 않는 O(N log N)의 속도. 그 첫 번째 주자는 "분할 정복(Divide and Conquer)"의 정석, 합병 정렬(Merge Sort)이다.
1. 분할 정복: "어려우면 쪼개라"
합병 정렬의 아이디어는 단순하다.
"10만 개를 정렬하는 건 어렵지만, 0개나 1개를 정렬하는 건 쉽다."
배열 [8, 3, 5, 1]을 예로 들어보자.
2. 핵심 로직: 정렬된 두 배열 합치기
합병 정렬을 구현하려면 먼저 "이미 정렬된 두 배열을 하나로 합치는 함수(merge)"가 필요하다.
이 과정은 두 배열의 맨 앞을 손가락(포인터)으로 가리키며 비교하는 것과 같다.
// 정렬된 두 배열(arr1, arr2)을 받아서 합쳐주는 함수
function merge(arr1, arr2) {
let results = [];
let i = 0; // arr1의 포인터
let j = 0; // arr2의 포인터
// 둘 다 아직 비교할 요소가 남아있을 때
while (i < arr1.length && j < arr2.length) {
if (arr2[j] > arr1[i]) {
results.push(arr1[i]); // 작은 쪽을 결과에 넣고
i++; // 포인터 이동
} else {
results.push(arr2[j]);
j++;
}
}
// 남은 요소들 떨이 처리 (이미 정렬돼 있으므로 그냥 다 넣음)
while (i < arr1.length) {
results.push(arr1[i]);
i++;
}
while (j < arr2.length) {
results.push(arr2[j]);
j++;
}
return results;
}
// 테스트: merge([1, 10, 50], [2, 14, 99, 100])3. 재귀(Recursion)로 완성하기
이제 merge 함수를 이용해 전체 정렬 로직 mergeSort를 만든다.
재귀 함수를 사용해 배열을 반으로 계속 쪼개고, 다시 merge로 합치면서 올라온다.
function mergeSort(arr) {
// 1. 종료 조건 (Base Case): 배열 길이가 1 이하면 이미 정렬된 것임
if (arr.length <= 1) return arr;
// 2. 반으로 쪼개기
let mid = Math.floor(arr.length / 2);
let left = mergeSort(arr.slice(0, mid)); // 재귀 호출
let right = mergeSort(arr.slice(mid)); // 재귀 호출
// 3. 정렬된 왼쪽과 오른쪽을 합쳐서 반환
return merge(left, right);
}
mergeSort([10, 24, 76, 73, 72, 1, 9]);4. 성능 분석: 왜 빠른가?
시간 복잡도: O(N log N) (무조건 빠름)
공간 복잡도: O(N) (치명적 단점)
합병 정렬의 유일한 약점은 메모리다.
slice로 배열을 자르고, results라는 새로운 배열을 계속 만들어내기 때문에 입력 데이터만큼의 추가 공간이 필요하다. 메모리가 부족한 임베디드 환경에서는 쓰기 어렵다.
핵심 정리
"속도는 빠르지만 메모리를 너무 많이 먹는데?"
크리스는 욕심이 생겼다. 속도는 O(N log N)으로 빠르면서, 메모리는 추가로 안 쓰는(O(1)) 꿈의 알고리즘은 없을까?
물론 있다. 다만 그 녀석은 조금 '불안정'하고 까칠하다.
전 세계에서 가장 많이 쓰이는 정렬 알고리즘의 왕, 퀵 정렬(Quick Sort)을 만나러 가보자.