시래 블로그

정렬 알고리즘 중 하나인 병합 정렬(Merge sort)에 대해 알아보겠습니다. 이 글은 《Introduction to Algorithms》 3th edition을 정리한 것입니다. 분할 정복 병합 정렬은 분할 정복(divide-and-conquer)라는 접근법을 이용하는 정렬 알고리즘입니다. 그렇기 때문에 분할 정복이 무엇인지 살펴봐야 합니다. 분할 정복은 문제를 작게 쪼개서 해결하는 방식입니다. 구체적으로는 다음 3단계를 거쳐 문제를 해결합니다. 분할(divide) 하나의 커다란 문제를 그보다 크기가 작은 하위 문제(subproblem)로 분할합니다. 하위 문제는 기존 문제와 크기만 다를 뿐, 같은 문제여야 합니다. 정복(conquer) 문제가 충분히 작아질 때까지 계속해서 하위 문제로 분할합니다. ..