점수로 정렬한 뒤 동점자의 기존 순서를 유지하려 합니다. 안정 정렬은 어떤 보장인가요?

안정 정렬은 비교 키가 같은 원소들의 입력 상대 순서를 정렬 뒤에도 보존하는 보장입니다. 점수가 같은 A와 B가 입력에서 A, B 순서였다면 결과에서도 A가 먼저여야 한다는 뜻입니다. 안정 정렬이 같은 점수의 원소를 사용자 ID순으로 정해 준다는 뜻은 아니며, 입력 순서가 달라지면 결과도 달라질 수 있습니다.

안정성과 결정성을 분리합니다

레코드 (점수, 이름)을 점수만 비교해 정렬할 때 점수가 같은 두 레코드의 이름 순서는 비교자가 결정하지 않습니다. 안정 정렬은 그때 원래 순서를 보존합니다. 이것은 객체가 완전히 같은지와 무관하게 비교 결과가 동등한 원소들의 상대 위치에 대한 규칙입니다. 이 보장을 안정성(stability)이라고 부릅니다. 비교자가 일관된 순서를 정의하지 않으면 안정 정렬도 모순을 고쳐 주지 못합니다. NaN처럼 비교가 비정상적인 값도 명시적인 정책이 필요합니다.

여러 기준을 적용할 때는 낮은 우선순위 기준부터 안정 정렬하고 높은 우선순위 기준으로 다시 정렬하면 앞선 동률 순서가 보존됩니다. 예를 들어 먼저 가입일 오름차순, 다음 점수 내림차순으로 안정 정렬하면 점수가 같은 그룹 안에서 가입일 순서가 남습니다. 또는 한 번에 (점수 내림차순, 가입일 오름차순, ID)라는 복합 키를 비교해 결과를 결정적으로 만들 수 있습니다. 분산 시스템처럼 입력 순서가 서버마다 다를 수 있으면 안정성보다 명시적인 보조 키가 재현성에 유리합니다.

라이브러리 계약과 사용 목적을 확인합니다

사용하는 정렬 함수가 안정적인지, 제자리 정렬인지, 추가 메모리를 얼마나 쓰는지 확인합니다. 안정 정렬은 상대 순서를 보존하지만 전체 결과가 입력과 무관하게 동일하다는 보장은 아닙니다. 입력 순서가 달라질 수 있는데도 동일한 랭킹을 원하면 ID나 이벤트 시각 같은 보조 키를 추가해야 합니다. 반대로 원래 순서 자체가 의미 있는 배치라면 보조 키로 덮어쓰지 않는 것이 맞습니다.

테스트는 동점 레코드에 입력 순번을 붙여 정렬 후 상대 순서를 확인하고, 정렬 기준을 두 번 적용한 결과와 복합 키 결과를 비교합니다. 제자리 여부·메모리·비교자의 일관성·특수 값 처리도 봅니다. 안정성은 성능 속성이 아니라 동등 원소의 순서에 관한 계약이며, 그 계약이 필요한 단계에서만 비용을 지불하겠습니다.

안정 정렬은 비교자가 동등하다고 판단한 원소의 입력 상대 순서를 보존합니다. 점수만 비교할 때 A, B가 입력 순서였다면 같은 점수 그룹에서도 A, B 순서가 남지만, 점수와 가입일을 모두 비교하면 가입일이 타이브레이커가 됩니다. 여러 번 안정 정렬한다면 낮은 우선순위 기준을 먼저 정렬해야 높은 기준의 동점 그룹에서 그 순서가 보존됩니다.

분산 병합에서는 각 입력 run의 순서만 보존해도 전역 입력 순서가 복원되지 않을 수 있으므로 원본 순번이나 명시적 사용자 ID를 보조 키로 전달해야 합니다. 다만 ID를 넣으면 ‘기존 순서 보존’이 아니라 결정적 전체 순서를 정한 것이므로 두 요구를 구분합니다. 정렬 함수의 안정성·제자리 여부·추가 메모리와 비교자의 일관성을 동점·NaN·병렬 병합 테스트로 확인하겠습니다.

비교 함수가 (점수, 가입일)을 모두 비교하면 점수만 같은 두 원소는 비교상 동등하지 않을 수 있습니다. 안정성이 보존하는 것은 전체 비교 결과가 동등한 원소들의 순서입니다. 테스트에서는 각 레코드에 원래 순번을 붙이고 동등 그룹마다 순번이 증가하는지 확인합니다. 비교 함수가 비추이적이면 정렬의 전제가 깨지므로 안정성 검사와 비교자 검증을 따로 두겠습니다.