[Algorithm] Merge Sort : 병합 정렬, 병합 소트 ( 코드 포함 )

입력된 배열의 중간지점을 찾은 뒤 반으로 나눈다.

그리고 나눈 전반부와 후반부를 각각 독립적으로 정렬한다 ( 재귀적으로 다시 반으로 정렬 )

마지막으로 전반부와 후반부를 병합한다.

 

병합정렬의 수행시간은 평균 O(n*log n)이고 최악의 경우에도 O(n * log n) 이다.

 

코드

 

이전까지 정렬함수와 다르게 정렬하고자 하는 부분의 시작인덱스와 끝 인덱스를 넣는다.

재귀적으로 되어있는데 merge는 분열되어 각각 정렬된 배열을 하나로 합치는 역할을 한다.

 

merge함수

 

 

결과