카운팅 정렬 (도수 정렬, 계수 정렬)

요소의 대소 관계를 판단하지 않고 정렬하는 알고리즘

 

시간복잡도는 일단 O(N)이다.

뒤에서부터 진행하면 안정적이다.

 

중간에 도수분포표/누적도수분포표에 해당하는 배열을 새로 사용해야 한다.

그리고 배열의 요소값의 범위에 따라 해당 배열의 길이가 달라진다!

즉, 정렬하는 요소수는 적은데 요소값의 범위가 엄청 크다면, 극단적으로 엄청난 메모리가 낭비된다.