任何只使用比較的一般排序算法的最壞情況下需要運行時間Ω(NlogN)，但是記住，在某些特殊情況下以線性時間進行排序仍然是可能的。
一個簡單的例子是桶式排序（bucket sort）。為使桶式排序能夠正常工作，必須要有一些附加的信息。輸入數據A1，A2，A3，…，AN必須只由小於M的正整數組成（顯然還可以對其進行擴充）。如果是這種情況，那麼算法很簡單：使用一個大小為M的稱為count的數組，它被初始化為全0。於是，count有M個單元或稱桶，這些桶初始化為空。當讀Ai時，count[Ai]增1。在所有的輸入數據讀入後，掃描數組count，打印出排序後的表。該算法用時O(M+N)。如果M為O(N)，那麼總量就是O(N)。
桶式排序的代碼如下：
public class A {
/**
* 輸入數據都小於M值，假如M默認值是10
*/
public static final int M = 10;
public static void main(String[] args) {
int[] count = new int[M];
/**
* 假設輸入數據是5，4，3，9，8，6，7
*/
Scanner sc = new Scanner(System.in);
System.out.println("請輸入小於"+M+"的整數");
while(sc.hasNextInt()){
int i = sc.nextInt();
if(i==0){
break;
}
System.out.println("輸入的數據是： "+i);
count[i] = i;
}
System.out.println("排序後count數組中元素：");
printCount(count);
}
/**
* @param count 元素都是正整數的int數組
*/
public static void printCount(int[] count){
for(int i=0;i<count.length;i++){
if(count[i]!=0){
System.out.print(count[i]+" ");
}
}
}
}
運行結果：
請輸入小於10的整數
5
輸入的數據是： 5
4
輸入的數據是： 4
7
輸入的數據是： 7
8
輸入的數據是： 8
2
輸入的數據是： 2
1
輸入的數據是： 1
0
排序後count數組中元素：
1 2 4 5 7 8
雖然這個算法似乎打破了下界，但事實上並沒有，因為它使用了比簡單比較更為強大的操作。通過使適當的桶增值，算法在單位時間內實質上執行了一個M-路比較。這類似於用在可擴散列上的策略。
該算法確實提出了用於證明下界的模型的合理性問題。這個模型實際上是一個強模型，因為通用的排序算法不能對於它可以期望見到的輸入類型做假設，而是必須僅僅基於排序信息做一些決策。很自然，如果存在額外的可用信息，我們應該有望找到更為有效的算法，否則這些信息就被浪費了。
盡管桶式排序看似太一般而用處不大，但是實際上卻存在許多其輸入只是一些小整數的情況，使用像快速排序這樣的排序方法真的是小題大作了。
