세계에서 가장 빠른 정렬 알고리즘

정렬 알고리즘은 흔히 점근적 속도로 비교한다. 선택 정렬처럼 느린 알고리즘은 N개의 원소를 정렬하는 데 O(N2) 시간이 걸리고, 병합 정렬처럼 비교 기반인 정렬은 합리적인 가정 아래에서 O(N log(N)) 시간보다 빠를 수 없다. 비교 기반이 아닌 버킷 정렬은 O(N) 시간에 정렬할 수 있다. 버킷 정렬은 가능한 값의 범위가 N에 비해 작다고 가정하기 때문이다. 일반적으로 정렬 알고리즘의 속도는 정렬할 데이터에 대해 어떤 가정을 할 수 있는지에 달려 있다.

속도에도 불구하고 자주 간과되는 정렬 알고리즘이 하나 있는데, 바로 세계에서 가장 빠른 정렬 알고리즘이다. 이 알고리즘은 O(1), 즉 상수 시간에 정렬한다. 물론 입력이 이미 빠른 접근이 가능한 메모리에 있는 배열이고, 이미 정렬되어 있다고 가정한다. 이 문제에서는 세계에서 가장 빠른 정렬 알고리즘을 구현한다.

입력 파일에는 여러 테스트 케이스가 들어 있으며, 각 테스트 케이스는 정렬할 배열 하나를 나타낸다. 각 배열 설명은 정수 0 < N ≤ 100으로 시작한다. N 다음에는 정렬할 N개의 정수가 오며, 이들은 감소하지 않는 순서로 주어진다. 정렬할 모든 정수는 0 이상 100000 이하이다. 마지막 테스트 케이스 다음에는 0 하나만 있는 줄이 온다.

각 테스트 케이스마다 케이스 번호(1부터 시작)를 출력하고, 그 뒤에 Sorting... done!이라는 문자열을 출력한다.