정렬된 수열을 라고 하자.
허용된 연산은 홀수 인덱스끼리의 교환과 짝수 인덱스끼리의 교환뿐이다. 따라서 어떤 원소가 홀수 인덱스에 있는지, 짝수 인덱스에 있는지는 바뀔 수 없다. 더 정확히 말하면, 홀수 인덱스에 놓인 값들의 멀티셋과 짝수 인덱스에 놓인 값들의 멀티셋은 각각 불변이다.
반대로, 홀수 인덱스에 놓인 값들의 멀티셋과 짝수 인덱스에 놓인 값들의 멀티셋이 정렬된 수열 에서의 멀티셋과 각각 같다면 정렬할 수 있다. 같은 홀짝성의 인덱스들 사이에서는 임의의 두 위치를 교환할 수 있으므로, 각 홀짝성 내부에서는 원하는 순열을 만들 수 있기 때문이다.
따라서 원래 수열 와 정렬된 수열 에 대해 홀수 인덱스의 값들을 모은 배열끼리 정렬하여 비교하고, 짝수 인덱스의 값들을 모은 배열끼리 정렬하여 비교하면 된다.
시간 복잡도는 정렬 때문에 이다.
