안정 정렬

같은 값끼리의 원래 순서가 정렬 후에도 유지되는 정렬(stable sort).

무슨 뜻인가

정렬 전 (입력 순서)                점수로 정렬
[김 90] [이 85] [박 90] [최 85]

안정 정렬  → [이 85] [최 85] [김 90] [박 90]
                ↑ 이가 최보다 먼저 (원래 순서 유지)

불안정 정렬 → [최 85] [이 85] [박 90] [김 90]
                ↑ 순서가 뒤바뀔 수 있다

같은 85점인 '이'와 '최'의 상대 순서가 보존되면 안정 정렬이다.

왜 중요한가 — 다중 기준 정렬

이 성질이 있으면 정렬을 여러 번 겹쳐 복합 정렬을 만들 수 있다.

• 목표: 부서별로 묶고, 부서 안에서는 연봉 높은 순

• ① 연봉으로 정렬 — ← 먼저 (덜 중요한 기준)

• ② 부서로 안정 정렬 — ← 나중 (더 중요한 기준)

• 부서로 묶이면서, 같은 부서 안에서는 ①의 연봉 순서가 그대로 유지된다

"덜 중요한 기준부터 정렬한다" 는 것이 핵심이다. 불안정 정렬이면 ②에서 ①의 결과가 흐트러져 이 기법이 성립하지 않는다.

실무에서는 이미 정렬된 목록에 사용자가 다른 컬럼 헤더를 눌렀을 때 이전 정렬이 부분적으로 살아 있는 자연스러운 동작이 여기서 나온다.

어떤 정렬이 안정한가

왜 갈리나 — 멀리 떨어진 원소를 건너뛰며 교환하면 순서가 깨진다. 퀵 정렬의 파티션, 힙 정렬의 루트-말단 교환, 선택 정렬의 최솟값 스왑이 모두 그렇다. 반면 병합·삽입 정렬은 인접한 것끼리만 비교·이동한다.

자바가 두 가지를 쓰는 이유 — 자주 나오는 질문

Collections.sort(list);      // TimSort  (병합 기반) → 안정
Arrays.sort(objectArray);    // TimSort              → 안정
Arrays.sort(intArray);       // Dual-Pivot QuickSort → 불안정

왜 기본형 배열만 퀵 정렬인가?

int[]에는 값만 있고 구별할 정체성이 없다. 3과 3은 완전히 같은 3이라 순서가 바뀌어도 결과가 동일하다. 안정성이 의미가 없으므로 메모리를 덜 쓰고 빠른 퀵 정렬을 쓴다.

객체는 같은 키라도 서로 다른 인스턴스이므로 안정성이 관찰 가능하다 → TimSort.

TimSort

파이썬과 자바가 쓰는 실무형 정렬이다. 병합 정렬 + 삽입 정렬 하이브리드로, 이미 정렬된 구간(run)을 찾아내 그대로 활용한다.

• 최선 O(n) — ← 거의 정렬된 데이터 평균·최악 O(n log n) 안정성 O

실제 데이터는 부분적으로 정렬돼 있는 경우가 많아 매우 잘 맞는다.

실무 함정 — 정렬 기준이 일관되지 않으면 예외

list.sort((a, b) -> a.score > b.score ? 1 : -1);   // 같을 때 0을 안 돌려줌
→ IllegalArgumentException: Comparison method violates its general contract!

TimSort는 비교자가 추이적이라고 가정하고 최적화한다. 계약을 어기면 런타임에 터진다. Comparator.comparingInt(...) 를 쓰는 것이 안전하다.