합병 정렬

[Algorithm] 합병 정렬(merge sort) 알고리즘

Merge sort Idea 합병 정렬은 하나의 리스트를 크기가 균등한 리스트 두 개로 분할하고, 각 부분 리스트를 정렬(정복)한 후 다시 합병하는 방식입니다. 구체적으로 단계를 나누면 다음과 같습니다. 분할(Divide): 주어진 리스트를 같은 크기의 부분 리스트 2개로 분할한다. 정복(Conquer): 더 이상 분할이 불가능할 경우, 주어진 부분 리스트를 정렬한다. 결합(Combine): 정렬이 완료된 부분 리스트들을 다시 하나의 완전한 리스트로 합친다. Example 위에서 살펴본 3단계 중, 1단계인 분할의 경우 주어진 리스트를 같은 크기로 2개 나누는 일이므로 특별한 연산이 필요하지 않습니다. 하지만, 2,3 단계의 경우 특별한 연산이 들어가고 사실상 하나의 단계로써 구현됩니다. 즉, 합병 정렬..