排序是計算機內經常進行的一種操作，其目的是將一組「無序」的記錄序列調整為「有序」的記錄序列。排序一般會有兩個操作，比較和移動，通過比較兩個關鍵字的大小確定兩個關鍵字的相對位置，再通過移動調整關鍵字位置。排序可分為內部排序和外部排序，若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內部排序，反之則稱為外部排序。如果是按照某個或某些關鍵字的大小，遞增或遞減的排列，且在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序後的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的，否則稱為不穩定的。