「計數排序（counting sort）」與「基數排序（radix sort）」可讓時間複雜度降為線性的 O(n)，比合併排序（merge sort）、堆積排序（heap sort）及快速排序（quick sort）都還要快，但僅能用於整數排列，且若使用時機不恰當，時間複雜度將會大幅升高。

計數排序（counting sort）

計算每筆資料出現次數後，再依照目標順序一一放入長度為 k 的陣列中。

圖示

現假設有 n=10 筆資料 [6,8,8,9,4,4,4,3,2,1] 要由小到大排列，依序有下列三大步驟：

1. 製作一長度為 k=10（索引值為 0~9）的陣列：
   
2. 計算每筆資料出現次數：
   
3. 將每筆資料依出現次數照順序放入陣列中：
   
   排序完成後結果如下：
   

時間複雜度

共可分為三大步驟討論：

1. 製作長度為 k 的陣列：時間複雜度為 O(k)。
2. 計算 n 筆資料出現次數：時間複雜度為 O(n)。
3. 把 n 筆資料依序排列至長度為 k 的陣列中：時間複雜度為 O(n+k)。

為了維持線性的時間複雜度，k 的值不能太大。

基數排序（radix sort）

將不同位元分開依序比較，比到最高位元後即完成排序。

圖示

現假設有 [264, 658,135] 三筆資料要由小到大排序，過程如下：

1. 將最低位數由小到大以「counting sort」排序：
   
2. 將次低位數由小到大以「counting sort」排序，原排好的最低位數也隨著調整：
   
3. 將最高位數由小到大以「counting sort」排序，原排好的較低位數也隨著調整：
   
   最終得結果為 [135, 264, 658]。

時間複雜度

每一位元都用「counting sort」排序，因此排序每位元時間複雜度皆為 O(n+k)；若設共有 d 位元要排序，時間複雜度為 O(d·(n+k))。

現設排序資料中最大者有 S 位數，再將 d 換底成 a，則 d=(logₐ S)，即 S 共有 (logₐ S) 位元，此時時間複雜度變為 O(d·(n+a))，將 d 以 (logₐ S) 代換，時間複雜度變成 O((logₐ S)·(n+k))。

根據經驗法則，若要使「(logₐ S)·(n+a)」為最小，k 應取 O(n)，時間複雜度 O((logₐ S)·(n+k)) 變成 O((logₙ S)·n)，在 S≤nᶜ、即未排序資料中最大者位元數量不超過資料個數時，O((logₙ S)·n)=O(c·n)，c 為常數，O(c·n) 為線性時間複雜度。

「radix sort」的時間複雜度為 O(c·n)，屬線性時間

如果未排序資料中最大者 S 的位元數遠比資料個數多（如共 5 筆資料要排序，但最大值 S 有 10¹⁰ 位元），「radix sort」要從最小位數排到 10¹⁰ 位元處，不僅無法維持線性的時間複雜度，還會大幅超越合併排序（merge sort）、堆積排序（heap sort）或快速排序（quick sort）等其他時間複雜度為 O(n·log n) 的排序演算法。