합병 정렬 (Merge Sort)

합병 정렬 : 합병 정렬은 분할 정복 기법을 사용한 정렬 알고리즘입니다. 리스트를 반복적으로 반으로 나누고, 각 하위 리스트를 정렬한 다음 정렬되 하위 리스트들을 합병하여 접체 리스트를 정렬합니다.

 - 합병 정렬은 항상 O(nlogn)의 시간 복잡도를 가집니다.

 - 합병 정렬은 추가적인 메모리 공간을 필요로 하며, 일반적으로 O(n)의 공간 복잡도를 가집니다.

 - 합병 정렬 은 불안정 정렬입니다. 동일한 값의 원소들이 입력 순서와 다르게 배치될 수 있습니다.

 

오름차순 예시

 

코드