[자료구조] 자바로 구현한 합병정렬

Merge Sort

 - 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.
 - 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다
 - 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
 - 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

 

복잡도  -

최악 , 평균, 최선의 경우 모두 

구현 -

 

 

 

결과 -