[백준][C] 2751번 수정렬하기 2 - 병합정렬

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절대값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 

5 5 4 3 2 1 

예제 출력 1 

1 2 3 4 5

 

문제점 -> 버블정렬(bubble sort) 또는 선택정렬(selection sort) 같은 경우는 시간 복잡도가 O(N^2) 이기 떄문에 시간안에 불가능하다 ( 수정렬하기1 과 다른점은 주어진 시간이 다르기 때문이다)

 

그래서 퀵소트나 병합정렬을 이용해서 푸는게 적절한데, 병합정렬을 처음 배워봐서 시도해 보았다.

 

소스

 

// 되어있는 것은 과정상 잘 이루어져 있는지 확인하는 테스트용 코드이다