前面讨论的排序算法，都假定要排序的所有数据在内存中都同时可用，如数组。要对存储在外部文件中的数据排序，首先要将数据送入内存，然后对它们进行内部排序。然而，如果文件太大，那么文件中的所有数据不能都同时送入内存。在大型外部文件中对数据排序，称为外部排序(external sort)。

堆排序是把数组看作堆，第i个结点的孩子结点为第 2i + 1和 2i + 2个结点（不超出数组长度前提下），堆排序的第一步是建堆，然后是取堆顶元素然后调整堆。建堆的过程是自底向上不断调整达成的，这样当调整某个结点时，其左节点和右结点已经是满足条件的，此时如果两个子结点不需要动，则整个子树不需要动，如果调整，则父结点交换到子结点位置，再以此结点继续调整。

假设有一组长度为N的待排关键字序列K[1….n]。首先将这个序列划分成M个的子区间(桶) 。然后基于某种映射函数，将待排序列的关键字k映射到第i个桶中(即桶数组B的下标i)，那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。 然后依次枚举输出B[0]….B[M]中的全部内容即是一个有序序列。

无论是冒泡排序，还是快速排序等等，都是基于元素之间的比较来进行排序。有一种特殊的算法叫做 计数排序，这种排序算法不是基于元素比较，而是利用数组下标来确定元素的正确位置。

快速排序的基本思想：通过一趟排序将待排数列分隔成独立的两部分，其中一部分数列的关键字均比另一部分的关键字小，则可分别对这两部分数列继续进行排序，以达到整个序列有序。 其中，最重要的partition主要有两种方法： 1)指针交换法。先把选定为pivot的元素放到最后，然后设定指针low和指针high，low指针右移，high指针左移，当两个指针相撞后停止移动。期间如果符合交换条件，两元素交换。最后把pivot元素放到中间。 2)挖坑法。类似冒泡排序的思路，把比pivot大的元素“往下沉”，把比pivot小的元素“往上浮”。

归并排序是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度，代价是需要额外的内存空间。 归并排序算法将数组每一次都分解为原来的一半大小的两个子数组，当分解到了右边界比左边界还大的时候，不再分解，开始排序。 然后将排序好的子数组逐级合并，最后得到的结果就是排序好的数组。

冒泡排序已经对算法进行有优化，但仍然不是最优。鸡尾酒排序又叫快乐小时排序，它基于冒泡排序又做了一点优化。博客中给出了鸡尾酒排序的优化版本。

冒泡排序算法多次遍历数组，在每次遍历中连续比较相邻的元素，如果元素没有按照顺序排列，则互换他们的值。 博客中先给出了朴素版本，再给出了优化了每一轮内循环结束点（减少遍历轮次）的needNextPass版本和isSorted版本，还有进一步优化判断边界的sortBorder版本，sortBorder版本为最优化版本。

希尔排序又叫缩小增量排序，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。 希尔排序是对插入排序的优化，基于以下两个认识：1.数据量较小时插入排序速度较快，因为n和n²差距很小；2.数据基本有序时插入排序效率很高，因为比较和移动的数据量少。 希尔排序的时间复杂度和增量的选择策略有关，博客中的选择策略会导致排序的不稳定性。

插入排序重复地将新的元素插入到一个排好序的子线性表中，直到整个线性表排好序。 遍历数组，遍历到i时，a0,a1,…,ai-1是已经排好序的，取出ai，从ai-1开始向前和每个比较大小，如果小于，则将此位置元素向后移动，继续先前比较，如果不小于，则放到正在比较的元素之后。可见相等元素比较是，原来靠后的还是排在后边，所以插入排序是稳定的。 当待排序的数据基本有序时，插入排序的效率比较高，只需要进行很少的数据移动。