초기 정렬도를 , 엄격한 역전 쌍의 수를 라 하자. 인접한 역전 쌍을 바꾸면 정렬도가 증가한다. 이면 삽입 정렬의 교환을 번 수행하여 를 달성한다. 그보다 클 때는 먼저 정렬한다. 같은 값이 있으면 정렬 후 인접하게 된 같은 값끼리 남은 횟수만큼 교환한다. 모두 다르면 같은 위치를 두 번 교환하여 두 번씩 소모하고, 남은 횟수가 홀수이면 정렬도 을 잃는다. 모든 값이 다를 때는 순열의 홀짝성 때문에 이 손실이 불가피하다.
시간은 , 정렬도는 최대 이다. 작은 서브태스크는 연산 순서를 모두 탐색하되 교환 시 정렬도 변화를 에 계산한다. 검사기는 정확히 개의 유효한 인덱스를 요구하고, 최댓값은 맞지만 결과 정렬도가 다른 경우에만 를 준다.
