4. 합병 정렬

합병 정렬은 주어진 n길이의 리스트에서 작은 집합을 여러개 만들어 비교하고

여러 집합을 병합해과는 과정에서 리스트를 정렬해나가는 방법이다.

 

 1. 분할단계는 리스트를 성분이 2개가 될 때까지 분할한다.

 2. 병합단계는 2개의 성분을 가진 리스트에서 정렬하여 병합된 리스트에 삽입한다.

 3. 모든 리스트가 주어진 길이 n이 될 때까지 병합을 반복한다

 

합병정렬의 방법 

출처: https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

합병 정렬 - 위키백과, 우리 모두의 백과사전

 

합병정렬은 분할과정과 병합과정에서 리스트 길이 n에 따른 동일한 시간을 소모하므로

시간복잡도는 O(nlogn) Ω(nlogn) 이 된다.