[알고리즘] 병합 정렬 (Merge Sort)

Merge Sort

<개념>

• 분할 정복 알고리즘 중 하나로 안정 정렬에 속하는 정렬 알고리즘이다.

• 리스트를 재귀적으로 반으로 나누고, 각 부분을 정렬한 뒤 다시 병합하는 과정으로 작동한다.

<특징>

• 모든 경우에 O(N log N) 시간복잡도를 가진다.

• 병합 과정에서 추가적인 배열이 필요해 O(N)의 메모리가 필요하다.

• 중복되는 원소들이 정렬 후에도 원래의 순서를 유지한다.

• 큰 데이터 세트나 안정성이 중요한 상황에서 효과적이다.

<단계>

<예시>

                              [38, 27, 43, 3, 9, 82, 10]
                      [38, 27, 43]             [3, 9, 82, 10]
                 [38, 27]       [43]        [3, 9]       [82, 10]
               [38]    [27]       [43]    [3]   [9]    [82]    [10]
					               (기본적으로 크기가 1이면 정렬 완료)