[알고리즘] 합병 정렬

합병 정렬 ( 출처 : https://ko.wikipedia.org/wiki/합병_정렬 )

 

일반적으로 구현했을 때 안정 정렬에 속하며, 분할 정복 알고리즘의 하나다.

 

합병 정렬 알고리즘의 구체적인 방법

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음,

두 개의 정렬된 부분 리스트를 합해 전체가 정렬된 리스트가 되게 하는 방법이다.

합병 정렬은 다음의 단계로 이루어진다.

• 분할 : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
• 정복 : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법을 적용한다.
• 결합 : 정렬된 부분 배열들을 하나의 배열에 합병한다.