병합 정렬

병합 정렬

병합정렬(Merge Sort)은 퀵정렬과 비슷한 시간 복잡도(nlog(n))을 가진 것 처럼 보이지만 퀵정렬에서는 최악의 경우에 N^2 의 시간 복잡도가 발생할 수 있다.

병합 정렬은 최악의 경우도도 nlong(n)의 시간 복잡도를 보장한다.  병합 정렬은 "분할정복  방법"을 채택한 알고리즘으로 일단 

"반으로 나누고 나중에 합쳐서 정렬하는 알고리즘 "이다 

분할 과정 

분할 과정

정렬되는 과정은 퀵정렬과 매우 유사하다.

합쳐지는 과정에서 정렬이 이루어 지는데 양쪽 시작점을 i 와 j 로 놓고 서로 비교하면서 임시 배열에다 저장한다.

그렇게 되면 배열의 길이만큼의 반복으로 정렬되는 새로운 배열을 얻을 수 있다.

 

합쳐지는 과정에서의 시간 복잡도는 N 이고 분할되는 시간복잡도는 logN이기 때문에 이 알고리즘의 시간복잡도는 Nlog(N)이라 할 수 있다.

merge_sort

분할 과정