합병 정렬(Merge Sort)

합병 정렬

여러 개의 자료의 집합을 결합하여 한 개의 정렬된 집합으로 만든다.

1단계

자료의 갯수가 하나가 될 때까지 반으로 쪼갠다.

자료의 갯수가 하나가 되면 쪼개는 작업을 멈춘다.

2단계

하나씩 정렬을 하면서 합친다. 

시간복잡도

Best, Worst, Average

실행코드 / 결과

실행결과를 보면 알 수 있듯이 재귀함수를 사용했기 때문에

전부 쪼갠 후 한 번에 합치는 것이 아니라 쪼개고 합치는 과정이 반복되는 것을 확인할 수 있다.