排序是算法的一个基本问题，很多问题都有排序的需要，因此高效的排序方法是大家一致追求的。插入排序与归并排序是两个常见的基本算法。
问题描叙：将一个无序的n个元素序列按从小到大（从大到小）的顺序输出
算法：插入排序的基本思想是:每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列;即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
插入排序
# insertion-sort(A) for j = 2 to A.length key = A[j] #insert A[j] into the sorted sequence A[1..j-1] i = j-1 while i>0 and A[i] > key A[i+1]= A[i] i = i-1 A[i+1] = key
归并法（分治法）
# merge(A.p,q,r) n1 = q-p+1 n2 = r-q let L[1..n1+1] and R[1..n2+1] be new arrays for i = 1 to n1 L[i] = A[p+i-1] for j = 1 to n2 R[j] = A[q+j] L[n1+1] = float(‘inf‘) #positive infitiny R[n2+1] = float(‘inf‘) i = 1 j = 1 for k = p to r if L[i]=< R[j] A[k] = L[i] i = i+1 else A[k] = R[j] j = j+1 # merge-sort(A,p,r) if p<r q = (p+r)/2 merge-sort(A,p,q) merfe-sort(A.q+1.r) merge(A,p,q,r)
插入排序算法时间约为c1n^2 , 归并排序的算法时间约为c2*n*lg(n), 对于小规模输入，插入排序更高效，对于大规模排序，归并排序更有优势。
原文：http://www.cnblogs.com/youyuan-wang/p/6403441.html