홀짝 정렬

정렬된 수열을 $B$라고 하자.

허용된 연산은 홀수 인덱스끼리의 교환과 짝수 인덱스끼리의 교환뿐이다. 따라서 어떤 원소가 홀수 인덱스에 있는지, 짝수 인덱스에 있는지는 바뀔 수 없다. 더 정확히 말하면, 홀수 인덱스에 놓인 값들의 멀티셋과 짝수 인덱스에 놓인 값들의 멀티셋은 각각 불변이다.

반대로, 홀수 인덱스에 놓인 값들의 멀티셋과 짝수 인덱스에 놓인 값들의 멀티셋이 정렬된 수열 $B$에서의 멀티셋과 각각 같다면 정렬할 수 있다. 같은 홀짝성의 인덱스들 사이에서는 임의의 두 위치를 교환할 수 있으므로, 각 홀짝성 내부에서는 원하는 순열을 만들 수 있기 때문이다.

따라서 원래 수열 $A$와 정렬된 수열 $B$에 대해 홀수 인덱스의 값들을 모은 배열끼리 정렬하여 비교하고, 짝수 인덱스의 값들을 모은 배열끼리 정렬하여 비교하면 된다.

시간 복잡도는 정렬 때문에 $O(N \log N)$이다.