작은 이동을 활용
작은 이동만 필요하면 삽입 정렬의 비교·이동 비용이 줄어듭니다.
기초 정렬은 입력 분포와 부작용 비용으로 선택한다
삽입, 버블, 선택 정렬은 모두 O(n²)이지만 거의 정렬된 입력, 조기 종료, 쓰기 횟수에서 선택 기준이 갈립니다.
교환 없음에 멈춤
한 pass에서 swap이 없으면 버블 정렬은 바로 종료할 수 있습니다.
쓰기 횟수를 줄임
저장 매체 쓰기 비용이 크면 선택 정렬의 교환 횟수를 비교합니다.
안정성
같은 키의 원래 순서가 필요한지 먼저 묻습니다.
반례
역순, 중복, 이미 정렬된 배열을 모두 실행합니다.
정렬 안정성·부작용 확장
n이 커지면 기초 정렬은 설명용 또는 작은 구간 최적화로
제한합니다.