대량의 정수 키를 정렬하려는데 값의 범위와 자릿수를 알고 있습니다. 계수 정렬이나 기수 정렬이 비교 정렬보다 유리한지 무엇을 기준으로 판단하나요?

계수 정렬과 기수 정렬은 키의 구조를 이용하므로 비교 정렬의 일반적인 O(n log n) 하한을 그대로 적용받지 않습니다. 그러나 계수 정렬은 원소 수 n뿐 아니라 값 범위 k에 비용이 좌우되고, 기수 정렬은 자릿수 수 d와 각 단계의 버킷 비용을 부담합니다. 따라서 ‘정수면 O(n)’이 아니라 범위·자릿수·메모리·안정성·키 표현을 함께 보고 선택하겠습니다.

범위·자릿수·안정성을 측정합니다

계수 정렬은 최소·최대 사이의 각 값에 카운터를 두고 빈도를 센 뒤 누적 위치로 출력합니다. 값이 0부터 100이고 원소가 수억 개라면 유리할 수 있지만, 원소가 백 개이고 값 범위가 수십억이면 카운터 배열이 낭비됩니다. 음수가 있으면 최소값을 빼서 인덱스를 만들되 범위 계산의 오버플로와 메모리 상한을 확인합니다. 이처럼 키의 범위 축을 직접 순회하는 방식을 범위 기반 정렬(range-based sorting)이라고 부를 수 있습니다.

기수 정렬은 키를 자릿수나 바이트 단위로 나누어 여러 번 분배합니다. LSD 방식으로 낮은 자리부터 처리할 때 각 단계가 안정적이어야 이전 단계에서 정한 낮은 자리 순서가 보존됩니다. 버킷 수를 크게 하면 단계 수는 줄지만 카운터 배열과 메모리 접근이 커지고 캐시에 맞지 않을 수 있습니다. MSD 방식은 높은 자리부터 나눠 가변 길이 키의 접두사별 처리가 자연스럽지만, 빈 버킷과 종료 조건이 달라집니다. 이를 비교 없는 정렬(non-comparison sorting) 계열이라고 부릅니다.

표현과 실제 비용을 검증합니다

부호 있는 정수, 음수, 가변 길이 문자열은 바이트의 사전 순서가 원하는 숫자 순서와 맞도록 변환해야 합니다. 객체 레코드를 정렬한다면 키만 이동할지 레코드 전체를 안정적으로 이동할지도 정합니다. 기수 정렬은 단계마다 임시 버퍼가 필요할 수 있고, 계수 정렬은 값 범위가 커질 때 메모리가 병목이 됩니다. 중복이 많아도 안정성을 요구하는지 확인하겠습니다.

테스트는 작은 범위·큰 범위, 음수·최대값, 중복, 가변 길이, 거의 정렬된 입력을 포함합니다. 비교 정렬을 기준 구현으로 결과를 맞추고, 실행 시간·카운터 메모리·임시 버퍼·캐시 누락을 측정하겠습니다. 키 구조를 활용하는 것이 유리한지 판단하려면 n만 표기하지 않고 k와 d를 비용의 일부로 드러내야 합니다.

계수 정렬은 값 범위 k의 카운터를 필요로 하므로 원소 수 n만 작다고 유리하지 않습니다. n=100이고 값 범위가 수십억이면 카운터 공간이 낭비됩니다. 기수 정렬은 자릿수 또는 바이트별 pass를 수행하며, LSD 방식에서 각 pass가 안정적이어야 앞선 낮은 자리의 순서가 보존됩니다. 음수는 인덱스 보정이나 부호 비트 변환을 정해야 합니다.

레코드 안정성이 필요하면 누적 카운터로 위치를 정하고 같은 키의 원래 순서를 보존하는 방향으로 입력을 순회해야 합니다. 버킷 수를 키우면 pass는 줄지만 카운터와 캐시 비용이 증가할 수 있습니다. 비교 정렬과 결과를 대조하면서 k·자릿수 d·임시 버퍼·메모리 대역폭을 실제 데이터 분포에서 측정하고, 가변 길이 키의 종료 규칙도 시험하겠습니다.

LSD 정렬의 예로 21과 12를 일의 자리로 정렬하면 21,12가 되고, 십의 자리로 안정 정렬하면 12,21이 됩니다. 11과 12처럼 높은 자리가 같은 값은 마지막 pass가 이전의 낮은 자리 순서를 보존해야 합니다. 누적 카운터의 끝 위치를 감소시키며 채운다면 입력을 뒤에서 앞으로 훑어 같은 키의 상대 순서를 보존하는 구현을 사용할 수 있습니다.