hong_mok

합병 정렬(Merge Sort) - 시간 복잡도 : O(n log n) - 분할 정복 알고리즘 이다. 알고리즘 - 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 - 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. - 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. - 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병(merge) 한다. - 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다. 과정 합병 정렬 과정을 그림으로 나타내면 다음과 같다. - 상단의 붉은색 부분은 정렬되지 않은 리스트들을 나누는 분할(devide) 과정이다. 길이가 1이..