000. 수 정렬하기(백준2750번)

문제

문제 분석하기

버블 정렬 = $O(n^2)$
병합 정렬 = $O(nlogn)$

위 시간복잡도를 알고있다고 가정하고 분석해보면

버블 정렬 = $1,000^2$ = $100,000,000$ (1억)
병합 정렬 = $1000log1000$ = $3,000$ (3천)

시간제한은 1초이다 즉, 1억번의 연산 안에 계산을 해야한다.
위 시간복잡도를 봤을 때 병합 정렬이 적합해 보인다.

손으로 풀어보기

주어진 리스트를 절반으로 분할하여 부분 리스트로 나눈다.
부분 리스트의 길이가 1이 아니라면 위 과정을 되풀이 한다.
부분 리스트끼리 정렬하여 합친다.

슈도코드 작성하기

long num = 수의 개수 입력 받기
long[] arr = new long[num]; // 정렬할 수들
for(int i=0; i<arr.length; i++) {
	arr[0] = 수 입력 받기
}
long[] temp = 정렬된 수들이 담길 배열

for(int i=0; i<num; i*=2) {
	for(int j=0; j<num-1; j += 2*i) {
	
	}
}