문제 조건을 보면 data[i] 중에 음수가 있을 수 있습니다. C에서 a % b 연산을 할 때 a가 음수라면 결과가 음수가 될 수 있습니다. (ex. -5 % 3 == -2) 따라서 (data[i] / tenth) % 10로 인덱스를 계산할 때 data[i]가 음수였다면 배열 인덱스 밖을 접근하게 됩니다. 이를 해결하는 가장 간단한 방법은 입력을 받을 때 모든 수에 충분히 큰 값을 더해버리는 것입니다.

그리고, 현재 66~71번째 줄에서 tenth가 max_value 이하일 동안 계속 10을 곱하는데, 여기서 오버플로우가 날 수 있습니다. (max_value가 10억일 경우, tenth가 10억일 때 while문을 한 번 더 실행하면 (10억 * 10)이 int 범위(약 21억)를 넘어가서 overflow) 따라서 모든 값을 long long으로 바꿔주어야 합니다.

+ 제가 이 두 가지를 고쳐서 내 봤더니 그래도 시간 초과가 납니다.. 다른 방법을 시도해보세요.
(C++ STL에 이 문제를 해결해주는 함수가 있긴 한데, 직접 풀어보고 싶으시다면 굳이 안 찾아보셔도 됩니다)

어떻게 이렇게 세심하게 보실수가있죠.. 대단하십니다... 시간복잡도는 말 그대로 이론상 복잡도군요, 메모리할당 복사 등 다 따지면 사실상 복잡도가 훨씬 높나보군요 ㅠㅠ

Radix Sort의 시간 복잡도를 정확히 말하면, 입력으로 들어오는 수를 B진법으로 표현했을 때 최대 자릿수를 D라고 하면 O(D(N+B))가 됩니다. 현재 구현에서는 B=10이라서 D가 9 정도 되는데, N이 500만이나 되기 때문에 B를 많이 키워도 N보다 작다면 별로 상관이 없습니다. B를 대충 4만보다 크게 정하면 D=2로 만들 수 있습니다.

B를 2^k꼴로 (예를 들어 2^16 = 65536) 정하면 더 좋은데, 그 이유는 그렇게 되면 (a / B) == (a >> k), (a % B) == (a & (B - 1))이 되기 때문에 연산 하나하나가 상대적으로 오래 걸리는 나눗셈/나머지 연산 대신 비트 연산자를 쓸 수 있기 때문입니다. (비트 연산자는 매우 빠릅니다)

이런 식으로 Radix Sort를 효율적으로 구현할 수 있습니다.

세상에 그러면 radix sort 라는게 10진법이라는 고정관념을 빼고,

예를들어 65536진법이라고 가정했을 경우

100000이라는 최대값을 계산하기 위해서는 반복을 약6번 해야됨가 다르게,

65536진법은 2번만 해도 radix sort 로 정렬될 수 있다는 말씀이신가요!?

네 그렇습니다. 그리고 비트 연산이랑 나눗셈/나머지 연산의 차이가 생각보다 많이 크기 때문에 최적화를 위해서는 되도록 비트연산으로 다 구현하는 것이 좋습니다.