归并排序是将两个有序表合并成一个有序表的过程，即把待排序序列分割成多个排好序的子序列，再合并成一个有序序列。该方法是分治法一个典型应用，类似与从两个排好序的纸牌中选择小的排成一个大的有序列。
例如有两个有序表：（7,10,13,15）和（4,8,19,20），归并后得到的有序表为：（4,7,8,10,13,15,19,20）。

归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。

Merge(A,p,q,r)
1    n1=q-p+1
2    n2=r-q
3    L(1...n1+1) and R(1...n2+1) as new arrays
4    for i=1 to n1
5        L(i) = A[p+i-1]
6    for i = 1 to n2
7        R(i) = A[q + j]
8    L[n1 + 1] = inf
9    R[n2 + 1] = inf
10    i = 1
11    j = 1
12    for k = p to r
13         if L[i] < R[j]
14            A[k] = L[i]
15            i = i + 1
16        else
17            A[k] = R[j]
18            j = j + 1

Merge-Sort(A,p,r)
1    if(p < r)
2         q = floor((p + r) / 2)
3        Merge-Sort(A, p, q)
4        Merge-Sort(A,q + 1, r)
5        Merge(A, p, q, r)