nomad-programmer

병합 정렬은 '분할 정복(divide and conquer)'이라는 알고리즘 디자인 기법에 근거하여 만들어진 정렬 방법이다. 분할 정복이란, 말 그대로 복잡한 문제를 복잡하지 않은 문제로 '분할(divide)'하여 '정보(conquer)'하는 방법을 말한다. 단 분할해서 정복했으니 정복한 후에는 '결합(combine)'의 과정을 거쳐야 한다. 즉 다음 3단계를 거치도록 알고리즘을 디자인 하는 것이 분할 정복법이다. 1단계 분할(Divide) : 해결이 용이한 단계까지 문제를 분할해 나간다. 2단계 정복(Conquer) : 해결이 용이한 수준까지 분할된 문제를 해결한다. 3단계 결합(Combine) : 분할해서 해결한 결과를 결합하여 마무리한다. 이 방법을 근거로 어떻게 병합 정렬 알고리즘이 디자인되었을까..