邱奕南，2014/11/30
註：以下測試數據，數值型資料均以五千萬筆為基準，字串資料或附加有字串
資料者，則以一千萬筆為基準，時間單位為秒。
一. 源起
排序，是許多核心效能的主要限制。關於排序的議題，個人在2005年已有研究
過一次（參見個人拙著：排序演算法專論），主要是整理並探討各種不同排序
演算法的理論效能，並實測加以證明，但對於細部的寫法並沒有太多著墨。本
文的目的，便是針對排序的細部寫法再做一次更深入的研究。
首先，排序程式的寫法一定要採用template型式的專用型物件，不能使用虛擬
繼承的通用型物件。這是因為專用型的寫法，比對或搬移資料，一次只需1個
clock；通用型的寫法，因為必須透過繼承的虛擬函數來達到不同資料的比對
與搬移，而一次函數呼叫需要8～38個clock，這之間的速度便差了約十倍以上，
速度必然快不起來。以下便是這兩種寫法的速度差：
通用型物件 專用型物件
----------------------------------
int32 11.81 4.91
因此對於需要講求高效率的程式部份，務必採用專用型，而非通用型寫法。而
為了了解個人所寫的排序程式優劣，以下便是和std::sort的效率進行比對：
std::sort 排序物件
------------------------------------
int8 1.63 2.34
int16 3.61 3.68
int32 5.68 4.91
int64 5.67 4.92
float 6.10 6.07
double 6.12 6.03
字串物件 9.34 7.12
排序演算法，對於通用型資料而言，最快的就是Intro Sort（由Quick Sort、
Insertion Sort、Heap Sort三種演算法所組成），這也是std::sort和個人寫
的排序物件所採用的主要演算法。不過std::sort對於Quick Sort的寫法有部份
不同：
1.傳統的Quick Sort多採用median-3，std::sort在40筆資料以上時，再進一步
採用median-9來挑分堆元素。在個人實測中，這部份的加強可略微加快一些
速度（非常細微），但若再繼續往上提升到media-27以上時，則效率會不升
反降，因此採用media-9是可以認同的。
2.傳統的Quick Sort在分堆時，是從左右最外邊往內掃瞄，但std::sort則是從
正中央往左右兩邊掃瞄，而且多加了一個比對運算，來進行相同元素的搬移。
雖然在有大量相同值的情況，排序上會較快一些，但因比對次數較多，對於
比對時間較久且不易相同的資料，時間反而會變慢。例如前述實測數據中，
int8值域只有256個，排序50M個，相同值的資料很多，std::sort的排序速度
便快了一些，但對於字串物件而言，速度就慢上不少，因此並不值得這樣改
進，因為基本上排序資料會有相同值的情況相當少見，而容易有相同值的數
值型資料，其實都有更快的演算法來處理（後述）。
雖然個人寫的排序物件和std::sort的速度相當（或說略快），但這並非排序速
度的極限。以下便是整個改良的過程，但有些心得可以先行提出：
1.演算法最重要，這點無庸置疑。
2.配合機器特性也非常重要：
(1)儘量循序存取記憶體，避免隨機存取，這部份的速度差可達25倍以上。此
外也要避免在不同超大記憶體區塊來來回回跳越存取，避免引發Page Fault
而降低了記憶體存取速度。
(2)儘量避免使用分支命令，以善用CPU的PreCache特性，其速度差可達一倍。
3.細微寫法可以儘量調整，速度相差大約在5～30%，不無小補。原則上就是儘
量減少運算量，例如簡單的運算儘量用inline而不用函數呼叫。又例如：
for (i=no-2; i>=0; --i) s[i+1] = s[i];
這種寫法在存取陣列s時，必須先存取i值，乘上元素大小，再加上陣列s的位
址後才能存取到需要的記憶體（大約8個clock），不如寫成（只需4個clock）：
for (s2=s+no-2; s2>=s; --s2) s2[1] = s2[0];
第2和第3點只能靠實測結果才能證實（經驗累積當然也有幫助），有時理論上
判斷應該會較快的寫法，但實測結果未必是對的，這些例子會在後面逐漸提到。
另外，為了追求最高效率，目前寫的排序函數並不管Stable的問題，亦即鍵值
相同時，位置次序可以任意為之。
二. 數值型單一陣列資料的排序
雖然對於通用型資料而言，Intro Sort是最快的排序演算法，但對於大量的數
值資料而言，最快的其實是Radix Sort，這部份拙著〔排序演算法專論〕已有
提及，只是一直未實作到個人的排序物件裡，此次剛好利用此一機會將之實作
出來：
Intro Radix
------------------------------
int8 2.34 0.17
int16 3.68 0.32
int32 4.91 0.74
int64 4.92 1.90
float 5.90 0.80
double 6.13 2.00
從前述數據可得到一個結論：在可接受的值域或精準度範圍內，應該儘量採用
較小的資料形態，例如可以用int16的就不用int32或int64，可以用float的就
不用double，不但佔用的記憶體空間較省外，排序也會較快。
雖然Radix Sort在資料量較多時排序比較快，但並不適用於資料量較少的情況，
此時便必須改用Intro Sort來排序，於是整合這兩者的資料量門檻值，便成了
最重要的一環。不同數值形態、不同資料特性、甚至不同的機器都會影響到此
一門檻值。目前個人的作法是在Windows作業系統上實測出最佳的門檻值，然後
再將之乘上2，以做數據誤差的緩衝（儘量使用不多費記憶體的Quick Sort）。
在實作Radix Sort的過程中，針對浮點數的部份，個人其實也花了一番心思。
原本個人以為浮點數不適合做Radix Sort，但仔細研究IEEE浮點數格式對應到
的整數位元組形式，其實只要做一點小轉換，便可以變成適於Radix Sort的鍵值：
inline uint32 GetRadixSortKey(const float& value)
{
int32 temp = *((int32*)&value);
if (temp < 0) temp ^= 0x7FFFFFFF;
return temp^0x80000000;
}
實測的結果，float的Radix Sort速度一直是int32（位元組數目相同）的兩倍
多，在嘗試良久後，才發現是if-then-else的分支命令所干擾。於是改寫計算
方式，將分支去除，速度就和int32相當接近了：
inline uint32 GetRadixSortKey(const float& value)
{
int32 temp = *((int32*)&value);
return temp^(((uint32)temp>>31)*0x7FFFFFFF)^0x80000000;
}
除了Radix Sort外，對於數值型資料是否有更快的排序法？答案其實只能說是
一半一半。因為適用小範圍數值的Distribution Counting Sort，它本身嚴格
說來並不能算是排序，因為它是採用數值計算來重新建出排序好的數值陣列資
料，並不帶有資料搬移的動作，因此不能有任何的附加資料，而且必須重複數
值相當多時才能顯現出它的效能，實際上並不算是實用的排序演算法。
傳統上，Distribution Counting Sort需要統計數值的範圍，才能決定是否適
合此一演算法。但統計數值的最大值與最小值，便必須掃一遍陣列，而這個時
間已足以拖慢整個排序的速度，並不值得。因此我們可以拿來排序已知數值範
圍較小的資料形態，如int8（256個數值）或int16（65536個數值），這樣就能
省下統計數值範圍的時間，而達到更快排序的效果（只是這個部份會用到的機
會其實相當地少）：
Intro Radix Counting
----------------------------------------
int8 2.34 0.17 0.05
int16 3.68 0.32 0.13
Distribution Counting Sort只需要對陣列進行一遍讀取和一遍寫入，便可排
好資料，已不可能有比它更快速的排序法了。
註：將Distribution Counting Sort的重建數值部份改成資料搬移，其實就等
同於Radix Sort。而以16位元做為鍵值長度的Radix Sort，無論在何種情
況，都慢於以8位元做為鍵值長度的Radix Sort（這點已經個人實測證明），
因此Distribution Counting Sort已無再研究改良的必要。
三. 數值型單一陣列資料排序前k筆資料
對於高數量的資料而言，無論什麼排序法都會耗時甚久，特別是鍵值結構很複
雜時（例如多階排序），排序的時間可能比排單一字串還要久。從最開始的實
測數據來看，排序一千萬筆字串便要耗時7秒多，若同時再有多個使用者進入操
作，勢必把伺服器忙爆了。如果使用者只需要前面一點點的資料，例如前20筆
或前1000筆，由於不必全部排完便可輸出，所需的時間應可大幅減少。本章主
要便是探討這部份的演算法。
和Intro Sort一樣，挑第k個大小元素的演算法，在通用型資料下，以Intro Select
最快，其觀念其實是完全一樣。因此要排好前k筆資料，只需仿造相同的演算法，
在分堆後，決定第k筆資料在那一堆並繼續反覆處理，另一堆則決定是否要全排
或捨棄（配合Intro Sort）。最佳情況可在2n次比對後得知第k個大小元素所在
位置，最差情況則是O(n^2)。
為了避免最差情況的發生，當遞迴層數到一定程度時，一樣必須改用其他方法。
與Intro Sort不同的是，Intro Select改以Median of medians方法挑中央元素，
而非使用HeapSort，因為HeapSort無論輸出多少排好的元素，固定需要O(nlogn)
的時間，並不符合挑k個元素最多只能O(n)的要求。反之，若排序最差情況改用
Median of medians方法挑中央元素，會造成執行時間大於O(nlogn)，一樣不符
合效率的要求。
Median of medians最常用的是5堆挑法，也分成由上往下的遞迴法，以及由下
往上的非遞迴法。遞迴法的觀念很簡單，就是平均分成5堆，遞迴挑出這5堆的
中央元素，最後再從這5個元素挑出中央元素。
int mom(int* data, int no)
{
if (no <= 5)
{
if (no <= 2) return data[0];
if (no <= 4) return median3(data[0],data[1],data[2]);
return median5(data[0],data[1],data[2],data[3],data[4]);
}
int step = no/5;
return median5(mom(data,step),mom(data+step,step),mom(data+step*2,step),mom(data+step*3,step),mom(data+step*4,no-step*4));
}
遞迴法的特點就是程式簡單，不用搬移元素，缺點就是效率較差，效果也較差
（捨棄不處理的元素較多）。非遞迴法則是每5個元素挑中央元素，將這些挑出
的中央元素視為一個陣列，再每5個元素挑中央元素，反複進行到最後剩下的元
素便是所需的中央元素。為了避免多使用一個陣列空間，5元素挑出的中央元素
可搬移到中央位置，以方便下一次處理時存取（間隔相等）。程式雖較複雜，
但無論效率或效果都會較好。只是因為帶有資料搬移的動作，因此當資料記錄
比較大時會較不適用（但基本上不該採用此一方式記錄資料，後面會再提及）。
遞迴 非遞迴
------------------------------
int32 0.325 0.256
至於數量很少的情況有兩種，一是總資料量很少，一是選擇數很少。前者可以
將之全部排序完，而不管選擇數有多少，畢竟它的量少，且只會處理一次，和
Intro Sort會處理很多次的情況並不相同，對於效率的影響微乎其微。後者則
以MinMax法最快（即Selection Sort的核心部份），其門檻值需要實測才能知
道，但從數理來推算，選擇2筆以下時必用MinMax法。以下便是各種數值形態的
Intro Select時間，由左到右分別為挑20筆、挑256筆、挑1/8～7/8筆數，最後
一個則是全排：
20 256 1/8 2/8 3/8 4/8 5/8 6/8 7/8 8/8
-----------------------------------------------------------------------
int8 0.35 0.35 0.56 0.83 1.09 1.39 1.64 1.90 2.14 2.34
int16 0.35 0.35 0.72 1.14 1.58 2.01 2.44 2.86 3.26 3.68
int32 0.35 0.36 0.90 1.47 2.06 2.65 3.25 3.83 4.39 4.91
int64 0.36 0.36 0.91 1.49 2.09 2.68 3.29 3.86 4.41 4.92
float 0.43 0.43 1.09 1.82 2.57 3.30 4.04 4.76 5.45 6.09
double 0.43 0.43 1.09 1.81 2.58 3.30 4.03 4.75 5.46 6.03
實測結果，確實依照選擇數而逐漸增減排序時間，效果良好。然而對於數值型
資料而言，Radix Select其實比Intro Select更快，就像Radix Sort快於
Intro Sort一樣。不過Radix Sort一般都是採用LSD法（從位低元組開始排起），
本身並不適用於挑選排序，必須改用較慢的MSD法（從高位元組開始）才行。
MSD Radix Select其實也是Bucket Select的一種，它是從高位元組開始，依照
數值將資料分成256堆，然後決定選擇的數量限制是落在那一堆，在該堆之前的
可以一次或分批排好，在該堆之後的則直接捨棄。然後再針對該堆餘下的資料
繼續以次高位元組處理，最佳情況是掃瞄一遍便可處理完，最差情況則是掃瞄
k遍（k=鍵值位元組數），基本上還是O(n)。以下便是各種數值形態的Radix Select
時間（前面加*星號的表示時間比全排還慢）：
20 256 1/8 2/8 3/8 4/8 5/8 6/8 7/8 8/8 Counting
------------------------------------------------------------------------------
int8 *0.17 *0.17 *0.17 *0.17 *0.17 *0.17 *0.17 *0.17 *0.17 0.17 0.05
int16 0.20 0.20 0.25 0.29 0.32 *0.39 *0.41 *0.51 *0.51 0.32 0.13
int32 0.25 0.25 0.34 0.42 0.50 0.59 0.68 *0.78 *0.85 0.74
int64 0.39 0.39 0.61 0.83 1.06 1.28 1.50 1.73 *1.96 1.90
float 0.34 0.34 0.43 0.51 0.61 0.63 0.77 *0.89 *0.98 0.80
double 0.52 0.52 0.74 0.95 1.17 1.42 1.70 1.92 *2.15 2.00
從實測數據裡，我們有三點需要探討：
第一是帶有Distribution Counting Sort的int8與int16，無論用Radix Select
挑多少資料，速度都比不上使用該排序法全排，因此這兩種數值形態在單一陣
列的情況下，便不需考慮Radix Select。不過當帶有其他非鍵值資料時，因已
無法使用Distribution Counting Sort，即便鍵值形態是int8或int16，仍必須
採用Radix Select，因此以下的分析仍必須包含int8與int16的數值形態。
第二便是實測數據裡，無論是那種資料形態，都有一些情況比全排還慢（前面
加星號者），這點可利用數理來加以推論說明。對於MSD Radix Select，每掃
一次需要的時間為：
257*8*s + b*n + k*x*n
其中s=設定1byte為0的時間，b=找出資料鍵值並丟入適當位置的時間，k=鍵值
byte數，x=拷貝1byte的時間。而Radix Sort的時間為：
O(n) = k*(257*8*s + b*n)
我們要找的是，選擇數量要在多少以上時，即便Radix Select是最佳情況，仍
會比Radix Sort全排還慢。也就是：
257*8*s + b*n + k*x*n + O(m) > O(n)
解開來可得：
m > n*(kb-b-kx)/kb - 2056s/kb
當n夠大時，常數項可略除。同時令p=kx/b，可得出：
m > n*(k-1-p)/k
依照現行的數值形態，會有四種情形：
k=1：m > -p*n，永遠成立，因此int8的資料不該採用Radix Select，必須全排。
k=2：m > n*(1-p)/2
k=4：m > n*(3-p)/4
k=8：m > n*(7-p)/8
如果不理p值的話，2 byte的int16至少在1/2以上要全排，4 byte的int32或float
在3/4以上要全排，8 byte的int64或double在7/8以上要全排。對照實測數據，
完全準確，表示這個數理分析是可信的。剩下的便是將p值實驗出來，並植入程
式中，如此Radix Select無論選擇數量多少，都不會再比全排慢了。
第三點要探討的是，8 byte的int64與double，當選擇數很小時，Intro Select
的速度會比Radix Select速度略快。那麼選擇數要小到什麼程度才應改用Intro Select
呢？嘗試用數理來分析，發現公式很複雜且不同情況有不同的公式，難以說誰
快誰慢。再者，利用另一台電腦再測試一次，結果反而變成Radix Select的速
度較快一些。由於兩者時間差距很小，因此可以不理，一律用Radix Select即可。
四. 數值型鍵值附帶其他資料的最佳結構
排序通常不是只用來排一個陣列資料，更多的運用都是藉由鍵值來排序其他資
料，得知其他資料的排名。鍵值和其他資料的組成結構，大致可分為四種：
1.集中形式：要排序的陣列裡直接記錄鍵值與其他資料。
2.指標形式：要排序的陣列裡只記錄資料所在的位址，這是教科書裡相當常用
的形式。
3.全部分離形式：也就是各項資料都自成一個陣列。
4.鍵值分離形式：由一個鍵值陣列和一個指標陣列所組成。
以下便是這四種結構帶不同附加資料的實測數據（鍵值均採用int32，前打星號
者為速度最快者）：
Intro Radix
------------------------------------------
集中
int32 *4.92 *1.39
int64 5.22 3.99
20 byte資料 6.30 8.93
指標
int32 14.51 44.62
20 byte資料 17.55 47.89
全部分離
int32 5.85 1.57
int64 *5.35 *1.90
int32/int32 6.25 2.13
int64/int64 6.28 2.87
20 byte資料 7.33 3.98
鍵值分離
指標 *5.35 *1.90
分析如下：
1.集中形式
若鍵值和附加資料的總和大小不超過機器的暫存器大小，那麼這種形式可說是
最佳的。但只要資料記錄大小超過機器的暫存器大小，這種形式其實就不值得
考慮了。
2.指標形式
雖然是教科書裡常用的形式，但非常訝異地，這種形式反而是最慢的，而且非
常之慢，完全不值得採用。
3.全部分離形式
如果附加資料只有一個陣列，且資料大小不超過暫存器大小時，其實速度也算
是最快的（等同鍵值分離形式）。但隨著陣列數漸多，或是陣列內的資料記錄
大小較大時，速度便會逐漸變慢。尤其是陣列數愈多，搬移時因為是跳越式存
取，愈容易導致Page Fault，使得速度愈來愈慢，特別是Radix Sort。例如一
個鍵值陣列帶兩個資料陣列時，以下的兩個寫法，一般大家都會認為寫法一比
較快，因為運算較少，但事實上寫法二才是比較快的（因為寫法一直接做兩個
大陣列的隨機存取，容易引發Page Fault）。這點可能會顛覆了很多人的想法。
(1)寫法一
DATA_TYPE1* k1 = source_data1;
DATA_TYPE2* k2 = source_data2;
for (KEY_TYPE* k=source_key; k> rotate_bit);
size_int index;
dest_key[index=pos_table[key]] = *k;
dest_data1[index] = *k1;
dest_data2[index] = *k2;
++pos_table[key];
}
(2)寫法二
int pos_table2[256+1];
memcpy(pos_table2,pos_table,257*sizeof(int));
DATA_TYPE2* k2 = source_data2;
for (KEY_TYPE* k=source_key; k> rotate_bit);
dest_data2[pos_table2[key]] = *k2;
++pos_table2[key];
}
DATA_TYPE1* k1 = source_data1;
for (KEY_TYPE* k=source_key; k> rotate_bit);
size_int index;
dest_key[index=pos_table[key]] = *k;
dest_data1[index] = *k1;
++pos_table[key];
}
以下為三個int32陣列的實測數據（Radix Sort）：
寫法一 寫法二
----------------------
5.96 2.13
可見錯誤的寫法所造成的效率差別有多大，在寫作講求效率程式時，實測是唯
一的證實方法，不能全由理論來主導，不然就會常有這種似是而非的寫法出現。
由於全部分離形式中，陣列數愈多，排序程式愈不易撰寫，效率也愈差，因此
建議最好不要超過三個陣列，否則便應該考慮改採其他結構來記錄處理。
4.鍵值分離形式
如果附加資料未超過機器的暫存器大小，可以考慮採用單純的雙陣列分離形式
來處理，否則就應該採用鍵值／資料指標的分離形式來處理，這部份和主資料
記錄的儲存方式無關。以效率上而言，主資料記錄應該採用陣列循序存放（無
論記錄有多大），當要排序時，才做成鍵值／資料指標（或索引值）的雙陣列
來排序。至於排完後要不要再重新將主資料記錄陣列儲存成循序結構，則見仁
見智。以下我們再做一些記憶體存取的測驗（存取一億筆資料）：
循序 隨機
----------------------
讀取 0.07 1.78
寫入 0.14 1.80
其中正向循序與反向循序存取的速度都是一樣的。由實測的數據可知，讀取的
速度差比寫入的速度差大，因此若要做隨機存取，以循序讀取、隨機寫入較佳，
優於隨機讀取、循序寫入的模式。這點也見於Radix Sort的寫法中（參見個人
拙著：排序演算法專論）。
由於隨機讀取的速度是循序讀取的25倍以上，因此若排序後的資料需要讀取兩
次以上，最好先做一次隨機讀取、循序寫入到新的循序陣列，然後再去使用新
的循序陣列，這樣的速度會比兩次隨機存取來得快。
綜合前述的分析，最佳的儲存結構為循序陣列：
1.資料記錄大小<=暫存器大小：採用循序陣列直接排序。
2.資料記錄大小>暫存器大小：採用循序陣列儲存，排序時再分拆出鍵值陣列與
指標陣列，排序後視情況可重整回循序結構。
五. 字串型單一陣列資料的排序
字串在傳統上都是以Intro Sort來排序，但因為字串本身就是指標形式，根據
前面的實測結果可以得知，這種結構用來排序，本身速度就是非常慢。以下便
是排序一千萬筆各種資料形態的速度，字串確實遠慢於其他數值型資料形態
（此處字串均為unicode字串）：
Intro Radix
------------------------------
int32 0.88 0.15
int64 0.90 0.38
float 1.11 0.16
double 1.10 0.40
uint64+ptr 1.11 0.70
英文字串 4.75
中文字串 3.99
字串排序之所以非常慢的原因，就是因為記憶體的隨機讀取，為了減少這種記
憶體的隨機存取，我們可以採用類似Bucket Sort觀念，將字串前幾個字元組成
一個數值（如uint64）的循序陣列結構，然後先以鍵值分離形式的雙陣列排序
好這個數值陣列與附加的字串陣列。接著再找出相鄰相同的數值形成一個區間，
最後再針對這個區間裡的字串資料做進一步的排序處理。若資料數還是很多的
便繼續採用Bucket Sort往下比對次幾個字元，否則便用Intro Sort將之排好。
以uint64的8位元組來講，一次可以記錄4個Unicode字元，或是8個Ansi字元，
大部份的情況都是在第一次的數值排序後，就差不多可以將所有字串全部區分
出來。因為排序的數值陣列都是循序存取，速度會遠比直接用隨機存取的字串
比對來得快。比較怕的情況就是字串前面幾乎都是相同的字元（例如網址字串），
對此，我們可以限定比對8個或16個字元後仍無法完全區分時，便直接轉由
Intro Sort處理即可。
以下便是傳統Intro Sort和我們改良過的Bucket Sort的字串排序實測數據，效
果可說相當顯著。多階排序，其實亦可比照辦理，效率絕對比單純的Intro Sort
快得多，只是需要額外的24*n byte的記憶體，這點要注意一下（五千萬筆的話
大約要多耗1.2GB的記憶體，不算不低）。
20 256 1/8 2/8 3/8 4/8 5/8 6/8 7/8 8/8
-----------------------------------------------------------------------
英文字串（26個字母）
intro 0.19 0.19 0.71 1.31 1.90 2.49 3.08 3.65 4.22 4.75
bucket 0.18 0.18 0.35 0.46 0.57 0.69 0.80 0.91 0.96 1.04
中文字串（1000個字）
intro 0.17 0.17 0.63 1.11 1.59 2.09 2.60 3.07 3.55 3.99
bucket 0.18 0.18 0.28 0.36 0.43 0.50 0.57 0.64 0.67 0.68
六. 字串型鍵值附帶其他資料的最佳結構
以下我們一樣實測了前述所提的四種資料組成結構（全部分離形式除外，因為
不可能會比其他形式快，前打星號者為速度最快者）：
Intro Bucket
------------------------------------------
集中
4 byte資料 *4.87 1.08
8 byte資料 *4.87 1.09
20 byte資料 5.08 1.35
指標
4 byte資料 5.98 *1.06
8 byte資料 5.99 *1.06
20 byte資料 6.63 *1.08
鍵值分離
指標 *4.95 1.22
結果和前述的數值型鍵值最佳結構有很大的出入。首先是指標形式不再是最慢
的，因為字串本身就是屬於指標形式。以下估算一下三種形式在進行Bucket Sort
所需額外的陣列數，和記憶體用量（s為附屬資料大小）：
陣列數 記憶體量 資料搬移方式
---------------------------------------------
集中 3 (16+s)*n memcpy
指標 3 24*n =
鍵值分離 4 32*n =
指標形式有著最少陣列數與最小記憶體用量，因此Bucket Sort是所有形式裡最
快的。集中形式雖然在4 byte時，記憶體用量比指標形式少，但因資料搬移方
式是比較耗時的memcpy，因此速度仍慢於指標形式。
至於Intro Sort部份，因為指標形式要取得鍵值需要做兩次隨機存取，因此它
的速度比起其他形式就慢了不少。但因主要的排序演算法是Bucket Sort，因此
綜整而言，仍以指標形式為最佳。
綜合前述的數值型鍵值的分析結果，最佳的結構依然是循序陣列。而在需要排
序時，依照鍵值的形態，數值型的便做出鍵值／資料指標雙陣列進行排序（若
資料大小很小的便直接排序），若是字串型的，便做出資料指標陣列直接排序。
七. 結論
以下為各種資料形態在改良前與改良後的實測數據：
改良前 改良後 倍差
----------------------------------
int8 2.34 0.05 46.8
int16 3.68 0.13 28.3
int32 4.91 0.74 6.6
int64 4.92 1.90 2.6
float 6.07 0.80 7.6
double 6.03 2.00 3.0
英文字串 4.75 1.04 4.6
中文字串 3.99 0.68 5.9
以最常用的int32與字串來看，大約加快了5倍左右的速度，成果算是相當不錯。
其他待研究的議題
1.多階排序如何避免直接從檔案取值比對
2.資料量超過記憶體負荷時的排序問題
3.分散式架構的合併／排序問題（m-way Merge）