안정 정렬은 비교 키가 같은 원소들의 입력 순서를 결과에서도 유지하는 정렬이다.
원리
안정성은 정렬 결과의 동률 처리 성질이다. 시간 복잡도나 오류 없이 실행된다는 일반적인 의미의 안정성과 구별한다.
예시
이름순으로 정렬한 직원 목록을 부서 기준으로 안정 정렬하면 같은 부서 안에서는 앞서 만든 이름순이 유지된다.
주의할 점
원래 입력 순서가 불명확하면 안정 정렬만으로 재현 가능한 결과를 얻지 못할 수 있다. 데이터베이스 결과처럼 입력 순서가 보장되지 않는 경우 명시적인 보조 키가 필요하다.