초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.
숫자 100만 개를 작은 수부터 늘어놓으려 합니다. 선택 정렬로는 비교를 5,000억 번쯤 해야 해서, 1초에 10억 번 비교한다 쳐도 8분이 넘게 걸립니다. 재귀로 문제를 작게 줄여 더 적게 비교할 수는 없을까요?
쉬운 문제부터 풀어 봅시다. 이미 작은 수부터 정렬된 줄이 두 개 있습니다. 이 둘을 하나의 정렬된 줄로 합치려면 어떻게 할까요?
가장 작은 수는 반드시 두 줄 중 한 줄의 맨 앞에 있습니다. 그러니 맨 앞끼리만 비교해 작은 쪽을 꺼내는 일을 반복하면 됩니다.
두 줄 모두 작은 수부터 정렬되어 있습니다.비교 0번
비교할 때마다 수가 하나씩 내려가니, 두 줄 길이의 합이 m이면 비교는 많아야 m − 1번, O(m)입니다.
정렬된 두 줄은 어디서 구할까요? 여기서 재귀를 씁니다. 배열을 반으로 나눠 각 절반을 같은 방법으로 정렬한 다음, 방금 본 방법으로 합칩니다. 값이 하나뿐인 조각은 이미 정렬된 것이니 기저 사례입니다.
출력 없음재생하며 lo와 hi 사이 구간이 반씩 줄었다가 합쳐지는 모습을 봅시다.
이처럼 문제를 작은 문제로 나누고, 각각 풀고, 그 답을 합치는 방법을 분할 정복(divide and conquer)이라 합니다. 분할 정복으로 정렬하는 이 방법이 병합 정렬(merge sort)입니다.
먼저 반씩 나눕니다.비교 0번
층마다 비교 횟수를 봅시다.
한 칸짜리 조각까지 나뉜 뒤 이웃끼리 합쳐 올라갑니다. 데모는 같은 층을 한꺼번에 합쳤지만, 실제 재귀 호출과 순서만 다를 뿐 비교는 같습니다.
한 층에서는 모든 값이 한 번씩 합친 줄로 내려가니 비교는 n번을 넘지 않습니다. 층은 반으로 나누기를 몇 번 해야 한 칸이 되는지, 즉 log₂ n개입니다.
그래서 전체 비교는 n log₂ n번을 넘지 않습니다. 병합 정렬은 O(n log n)입니다. 시간 복잡도 글의 데모에서 예가 비어 있던 줄입니다. 숫자 100만 개도 비교가 2,000만 번을 넘지 않아 0.02초면 됩니다.
병합 정렬이 약 9.2배 적게 비교합니다.
n이 8이면 선택 정렬 28번, 병합 정렬 15번으로 차이가 작지만, 2,000이면 약 100배가 됩니다.
공짜는 아닙니다. 합친 결과를 담을 줄(코드의 tmp)이 따로 필요해 원래 배열만큼의
메모리를 더 씁니다.
서로 다른 값 8개를 글의 merge_sort로 정렬합니다. 두 줄을 합칠 때는 맨 앞끼리 한 번 비교해 작은 쪽을 내리고, 한 줄이 비면 남은 줄은 비교 없이 그대로 붙입니다. 처음 순서를 잘 고르면 비교는 모두 몇 번까지 줄어들까요? 숫자로 답하세요.