Merge Sort(병합 정렬)은 존 폰 노이만(John von Neumann)에 의해 처음 소개(1945년)된 정렬 방법으로 원소 개수가 1 또는 0이 될 때까지 두 부분으로 자른 순서의 역순으로 크기를 비교해 병합해 나가는 정렬 방법입니다.

병합된 부분 안은 이미 정렬되어 있으므로 전부 비교하지 않아도 제자리를 찾을 수 있습니다. 대표적인 분할 정복(Devide and Conquer) 알고리즘으로 노이만의 천재성을 느낄 수 있게하는 안정 정렬 알고리즘 입니다.

위의 그림을 참고하면 Merge Sort를 더욱 쉽게 이해하실 수 있을 것 입니다. Merge Sort를 구현하는 프로그램을 작성하십시오.

입력

첫 줄에 입력할 수의 개수 N

다음 줄에 공백으로 구분하여 N개의 정수 입력

출력

Merge Sort 알고리즘으로 정렬이 완료된 상태를 출력