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

원소 개수가 1이 될 때까지 분할 한 뒤 분할한 역순으로 순서에 맞추어 병합 합니다.

분할

병합

while(true)

  정렬된 두배열을 하나의 배열의 끝에 다다를 때까지 순서대로 결과 배열에 넣는다.

이후 남은 배열을 결과 배열에 넣는다.

시간복잡도: O(nlogn)

장점

- 평균적으로나 최악의 경우에나 O(nlogn)의 복잡도를 갖는다.

- 연결 리스트의 정렬에 최적의 선택이 될 수 있다.

단점

- 추가 공간이 필요하다. 

코드