병합 정렬

병합 정렬은 기본적으로 분할 및 정복 방식을 따르며

정렬되지 않은 배열을 두개의 서브 배열로 분리하여 각 서브배열의 크기가 1이 될 떄까지 재귀적으로 분할하여 정렬하는 방식

방법

서브 배열의 크기가 1이 되면 동등한 레벨에 위치하는 크기가 1인 서브 배열과 서로 순서를 정리하여 병합한다.

배열의 길이가 0또는 1이 되면 이미 정렬된 것으로 판단한다.

그렇지 않은 경우 정렬되지 않은 배열을 반으로 잘라 두 개의 서브 배열로 분리한다.

탐색시간

O(nlogn)