[codeup] 3014. 정렬을 빠르게

https://codeup.kr/problem.php?id=3014

정렬을 빠르게!

1. 문제

데이터를 정렬하라.

 

2. 알고리즘

시간복잡도 O(NlogN) 정렬 함수를 구현하여 정렬해보자.

3. 주의할 점

sort함수를 사용하면 안되고, 데이터의 개수가 최대 450만개이므로 O(N^2) 정렬을 수행하면 절대로 풀 수 없다. O(N^2)으로 100만개 데이터를 정렬하면 100만 * 100만 = 10000000000000000(일조)번 연산을 수행하지만 O(NlogN)은 100만 * 20 = 20000000(2천만)번 연산을 수행한다. 

 

cf. 일반적으로 logN은 밑이 10인 상용로그를 말하지만 컴퓨터 과학에서는 밑이 2인 로그를 말한다.

 

4. 소스코드