정렬이 Comparison method violates its general contract!로 죽은 이유

문제 발생

우선순위 정렬이 운영에서만, 그것도 목록이 커졌을 때만 실패했습니다.

list.sort((a, b) -> a.priority() - b.priority());

java.lang.IllegalArgumentException: Comparison method violates its general contract!

같은 코드가 작은 목록에서는 몇 달 동안 멀쩡했습니다.

원인 분석

비교자가 계약을 어겼습니다. Comparator javadoc은 구현자가 지켜야 할 것을 세 가지로 못박습니다.

• 부호 대칭 — 모든 x, y에 대해 signum(compare(x, y)) == -signum(compare(y, x))를 보장해야 합니다.
• 추이성 — compare(x, y) > 0이고 compare(y, z) > 0이면 compare(x, z) > 0이어야 합니다.
• 일관성 — compare(x, y) == 0이면 모든 z에 대해 signum(compare(x, z)) == signum(compare(y, z))여야 합니다.

위 코드의 a.priority() - b.priority()는 뺄셈 오버플로로 첫 번째 규칙을 깹니다. 값이 Integer.MIN_VALUE 근처로 가면 부호가 뒤집혀 "a가 b보다 크고, b도 a보다 크다"는 상태가 만들어집니다.

작은 목록에서 안 걸린 이유는 정렬 구현에 있습니다. List.sort의 구현 노트는 Tim Peters의 TimSort에서 가져온 안정 적응형 병합 정렬이라고 밝히는데, 이 알고리즘은 어느 정도 크기 이상에서 병합 구간을 검증하다가 모순을 발견합니다. 그래서 javadoc의 Throws에도 **(선택적) 비교자가 Comparator 계약을 어긴 것이 발견되면 IllegalArgumentException**이라고 적혀 있습니다 — **"선택적"**이라는 말이 핵심입니다. 못 잡으면 예외 대신 조용히 잘못 정렬된 결과가 나옵니다.

해결 방안

1. 뺄셈 대신 비교 메서드를 씁니다. 오버플로가 원천적으로 없습니다.

list.sort(Comparator.comparingInt(Task::priority));

2. 여러 기준은 thenComparing으로 잇습니다. 직접 if를 엮다 보면 추이성이 깨지기 쉽습니다.

list.sort(Comparator.comparingInt(Task::priority)
                    .thenComparing(Task::createdAt)
                    .reversed());

3. null을 임의로 0 취급하지 않습니다. "null은 아무와도 같다"는 규칙은 일관성을 즉시 깹니다. Comparator.nullsFirst/nullsLast로 위치를 명시합니다.

4. 가변 상태나 시간에 의존하지 않습니다. 정렬 도중 값이 바뀌면 같은 두 원소의 비교 결과가 달라져 계약이 깨집니다. compare 안에서 현재 시각을 읽는 코드가 대표적입니다.

5. 부동소수점 비교는 Double.compare를 씁니다. a - b > 0 방식은 NaN에서 전부 false가 되어 대칭성이 무너집니다.

6. 정렬과 동치의 의미를 구분합니다. javadoc이 경고하듯 equals와 일치하지 않는 순서를 부여하는 비교자를 정렬된 Set/Map에 쓸 때는 주의해야 합니다 — 정렬은 되는데 contains가 실패하는 상황이 여기서 나옵니다.

공식 문서

• Java: Comparator
• Java: List.sort(Comparator)