3.2 - Elementary Sorting

Internal Sorting: 可將資料全部置於memory中進行排序

External Sorting: 資料量大，無法一次全部置於memory中進行排序，必須藉助外部儲存體保存資料，再進行排序(Merge Sort、M-way Search Sort、B Tree)

Stable、Unstable Sorting: 在input data中，可能會有多筆相同的值 $k,\ k^{1},\ k^{2}...$ ，若保證 $k$ 一定在 $k^{1},\ k^{2}...$ 前面，則稱為Stable Sorting。

1. Elementary Sorting

平均時間複雜度為: $O(n^2)$

1. Insertion Sort

2. Selection Sort

3. Bubble Sort

4. Shell Short