[Algorithm / Sort] 기수정렬(Radix Sort)

O(dn) 속도의 기수정렬(Radix Sort) 알고리즘이다.

아래 사진과 같이 특정한 시작점(오른쪽 또는 왼쪽)을 기준으로 점진적으로 정렬하는 것이 기수정렬이라고 한다.

LSD(least significant digit)    : 오른쪽을 기준 정렬

MSD(most significant digit)  : 왼쪽 기준 정렬

기수 정렬시 주의할 점은 각 단계는 전 단계의 정렬된 배열을 기준으로 해야한다는 것이다.