합병 정렬

합병 정렬은 분할 정복 알고리즘을 이용한 정렬 방법이다.

분할 정복은 큰 문제를 작은 문제로 쪼개어 작은 단위의 문제를 먼저 해결하면서 병합시켜 마지막으로 가장 큰 문제를 해결하는 문제 풀이 방법이다.

합병 정렬의 과정은 크게 배열을 분할하는 부분과 분할된 배열을 다시 합병하는 부분으로 나뉘어 진다.

분할에서는 배열을 두 개의 배열로 분할한다.
합병에서는 두 배열을 정렬을 하면서 합친다. 

시간복잡도는 분할에서 log2(N), 합병에서 N으로 분할이되는 만큼 다시 합병하기 때문에 둘을 곱하여 N*log2(N)이 된다.

성능이 선택, 버블, 삽입 정렬과 비교하여 효율적이고 안정적이기 때문에 자주 사용되는 정렬 방법 중 하나이다.
Java의 Arrays.sort() 및 Python sorted() 또한 합병 정렬과 삽입 정렬의 조합으로 작동한다.