内部排序（internal sorting）：排序工作在主存中完成。
外部排序（external sorting）：在磁盘或磁带中完成。
插入排序o(N^2)，希尔排序（Sellsort）o(N^2)。
可以让排序对象实现Comparable接口，通过重写它的CompareTo方法来实现比较。在这些条件下的排序叫做基于比较的排序（comparison-based sorting）。在默认的排序没有或不可接受的情况下，我们很容易用Comparator来重写排序算法。
插入排序由N-1趟排序组成。对于p=1到N-1趟，插入排序保证从位置0到位置p上的元素为已排序状态。插入排序利用了这样的事实：已知位置0到位置p-1上的元素已经处于排过序的状态。下面显示了一个数组样例在每一趟插入排序后的情况。
每趟后的插入顺序：
上图表达了一般策略。在第p趟，我们将位置p上的元素向左移动，直到它在前p+1个元素中的正确位置被找到的地方。下面程序实现了插入排序，位置p上的元素存储于tmp，而（在位置p之前）所有更大的元素都被向右移动一个位置。然后tmp被置于正确的位置上。
public static <AnyType extends Comparable<? super AnyType>> void insertionSort(AnyType[] a){ int j; for(int p=1;p<a.length;p++){ AnyType tmp = a[p]; for(j=p;j>0&&tmp.compareTo(a[j-1])<0;j--){ a[j] == a[j-1]; } a[j] = temp; } }由于嵌套循环的每一个都花费N次迭代，因此插入排序为o(N^2),而且这个界是精确的，因为以反序的输入可以达到该界。精确计算得出，上面程序内循环中元素的比较次数对于p的每个值最多是p+1次。对所有的p求和得到总数为：
2+3+4+...+N=o(N^2)
另一方面，如果输入数据已预先排序，那么运行时间为o(N)，因为内层for循环的检测总是判断不成立而终止。事实上，如果输入几乎被排序，那么插入排序将运行的很快。插入排序的平均情形也是o(N^2)。
