\(N\)개의 수가 주어졌을 때, 이들을 오름차순 으로 정렬하는 프로그램을 작성하시오. 같은 수가 여러 번 주어질 수 있다.

이번에는 \(N\)이 최대 \(100\,000\)까지 커지므로, 시간 복잡도가 \(O(N^2)\)인 정렬로는 제한 시간 안에 끝낼 수 없다.

⚠️ 주의. 이 문제의 채점 데이터에는, 피벗을 고정된 규칙으로 고르는 직접 구현한 퀵정렬을 일부러 \(O(N^2)\)로 망가뜨리도록 설계된 입력이 들어 있다. 첫 원소·끝 원소·가운데 원소를 피벗으로 쓰는 경우는 물론, 세 원소의 중앙값(median-of-three) 을 피벗으로 쓰는 영리한 퀵정렬까지 저격하는 입력이 포함된다 (이미 정렬된 수열, 모두 같은 수, 산(山)·골짜기 모양 수열, 매킬로이(McIlroy) 적대 수열 등).

따라서 최악의 경우에도 \(O(N \log N)\) 을 보장하는 정렬(병합 정렬, 힙 정렬, 또는 인트로정렬을 쓰는 C++ std::sort·자바 Arrays.sort(원시형은 듀얼피벗이라 주의)·파이썬 sorted() 같은 표준 라이브러리 정렬)을 사용해야 한다.

• \(1 \le N \le 100\,000\)
• \(-10^9 \le A_i \le 10^9\)
• 같은 수가 여러 번 주어질 수 있다.

첫째 줄에 수의 개수 \(N\)이 주어진다.

둘째 줄에 \(N\)개의 정수 \(A_1, A_2, \dots, A_N\)이 공백으로 구분되어 주어진다.

첫째 줄에 정렬된 수들을 오름차순으로, 공백으로 구분하여 출력한다.

riseoj 작성

출처 Original