基數排序有時也被稱作卡片排序，也是一種時間復雜度為O(n)的排序。為了給一個序列排序，基數排序需要大約相當的輔助空間(通常使用隊列)，可見空間復雜度為O(n)。 假設有一個無序序列含有n 個整數，整數的基數是k，最大有d 位(例如： 對于十進制整數而言， k = 10，可能的值是 0, 1, 2, ..., 8, 9，在 32 位系統上 d≤10，在64 位系統上 d≤20)，則基數排序的時間復雜度為O(d(n+k)) = O(n)。當對整數排序時，使用10進制雖然比較容易理解，但是速度慢(因為為了得到各位數字需要做除法和取模等操作)，為了盡可能的減小時間開銷，通常使用2 的指數次冪進制(例如：2, 4, 8, ..., 2r，r為2進制的冪)，這樣可以借助位移運算減小耗費CPU 指令數，提升運行速度。對于b位(在PC機上， b通常為32或64)的整數而言， d = b/r， k = 2r，于是時間復雜度O(d(n+k)) = O(b/r(n+2r))，理論上，當b/r(n+2r)最小時，速度應該最快。

以一個隨機整數序列為例，基數排序的過程見下表。

178 207 982 510 477 295 963 095 274 614 810 579 700 618 301 766

待排序序序列

510 810 700 301 982 963 274 614 295 095 766 207 477 178 618 579 

個位排序結果

700 301 207 510 810 614 618 963 766 274 477 178 579 982 295 095

十位排序結果

095 178 207 274 295 301 477 510 579 614 618 700 766 810 963 982

百位排序結果

以上是以基數為10進行排序的例子，實現時應該使用2的指數為基數，從而避免除法和取模而采用位運算來獲取較快的處理速度。
以下基數排序使用256個隊列，對int類型的序列從小到大排序，但是還是比快排慢一些，其實用多少隊列都比不上快排快。即使不用動態隊列，都用靜態隊列，還是比快排慢。根本原因在于這種基數排序的思想跟現代CPU架構背道而馳，非常的不CPU cache friendly.從一個隊列換到另一隊列，然后再換回來，這種換來換去的機制導致CPU cache line不停的被重新填充，畢竟內存的延遲和訪問速度比CPU cache要慢的多，大部分時間都耗費在這里。結果這種看上去很理想的所謂的O(n)算法，只能徒有虛名。相信這些是那些純搞理論的算法專家和數學家永遠都想不明白的！其實還不止基數排序如此，類似行為的計數排序和桶排序也快不起來，盡管它們的時間復雜度都是一色的O(n)。

 1 #include <queue> // use standard queue
 2 // non-portable implementation for LSD radix sort, for type int, 32 bit system
 3 template <typename ForwardIterator>
 4 void radix_sort(ForwardIterator first, ForwardIterator last)
 5 {
 6   // R: radix, K: k base, M: mask, B: ? bit system
 7   const unsigned R = 8, K = 1 << R, M = K - 1, B = 32;
 8   std::queue<int> q[K];
 9   for(unsigned i = 0; i < B; i += R)
10   {
11     for(ForwardIterator dit = first; dit != last; ++dit)
12     q[(*dit >> i) & M].push(*dit);
13     ForwardIterator cit = first;
14     for(unsigned j = 0; j < K; ++j)
15     while(!q[j].empty())
16     {
17       *cit++ = q[j].front();
18       q[j].pop();
19     }
20   }
21 }