분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하여 합치는 알고리즘이다.
시간 복잡도 평균 값은 O(nlogn)이다.
기수 정렬은 값을 비교하지 않는 특이한 정렬이다. 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교한다. 기수 정렬의 시간 복잡도는 O(kn)으로 여기서 k는 데이터의 자릿수를 의미한다.