Sorting

• 內部排序(internal sort): 將資料全部載入主記憶體，排序的處理動作全都在主記憶體進行
• 外部排序(external sort): 當資料量太大無法全部載入主記憶體，因此將資料儲存於輔助記憶體的工作空間中，在分段將資料載入主記憶體進行排序

• 比較式排序(comparison sort): 排序時是比較兩筆資料大小再決定如何移動資料的排序方式
• 分布式排序(distributive sort): 根據鍵值計算分分析出資料所應存放的位置，直接將資料放入該位置的排序方式

• key 相同的 reocde，在排序完成後仍維持原來的先後次序。
• 即 k_i = k_j，且 i < j，在排序後 R_i 仍排在 R_j 之前，此種排序為穩定排序 (stable sort)
• 反之若不能保證 key 相同的 record 排序後的順序則為不穩定排序 (unstable sort)

排序後資料 a₁ ~ a_n，其反轉表為 b₁ ~ b_n，而 b_i 表示在原始資料序列中，在 a_i 之前大於 a_i 的資料筆數

Example:

原始資料: 5, 3, 8, 2, 6, 1, 9, 7, 4

反轉表 (inversion table):