如果有一个随机排列的整数表，怎样将它排序呢？这是生活中也经常碰到的问题。比如给一组牌排序，我们通常会怎样做呢？
不断从原序列中取出元素来排成一个新序列，在新序列形成的时候保证它有序，这就是插入排序的办法。插入排序需要有空间存放和操作新序列，这可以在原序列的空间中满足。插入排序需要大量的比较和移动，量级是O(n*n)。我们也可以每次从现有元素中取出最小元素，这样新序列排下来自然是有序的，这就是选择排序的办法。选择排序需要O(n*n)的比较，最坏最好情况下都一样。这是一个缺点，和与之对称的插入排序比较，选择排序对原序列的情况缺乏适应性，冒泡排序是对此的改进。冒泡排序也基本使用原序列的空间，每次在现有元素中进行比较以寻找最小元素，并通过交换逐步把它移到相应位置。冒泡排序在原序列的基础上逐步调整得到新序列，它可以更加适应原序列的情况，在最好情况下时间为O(n)。这三种排序是最基本的，其它方法都是从各种角度对它们进行改进。
三种基本排序都着眼于从原序列形成新序列的过程。这是最基本的，但还可以把整个过程用分治或渐进的思想来处理。具体的改进方法有多种，希尔排序，快速排序，归并排序等等，我们现在可以欣赏它们的思想，但是当初每种方法的发现都是重要的成果，需要对排序问题有扎实的认识，也需要创造的灵感。
希尔排序把原序列分组，每一组进行插入排序，从较小的分组开始逐渐扩大，直到整个序列作为一组。分组元素是间隔选取的，较小的分组排序完成后，整个序列就在一个较大的尺度上有序了，随着分组的扩大，序列在越来越小的尺度上有序，直到完全有序。希尔排序利用插入排序对乐观情况的适应性，自顶向下渐进处理，避免了直接在小尺度上进行处理的盲目性。
归并排序反映出一种自底向上的分治思想，其时间为O(n*log(n))。
快速排序采用了自顶向下的分治思想，其做法和归并排序有某种对称性。
基数排序也是自顶向下的分治思想，它从关键字本身衡量问题的解决程度。