MERGE(A, p, q, r),其中A是个数组，p, q和r是下标。满足p<=q<r.该过程假设子数组A[p..q]和A[q+1..r]都已排好序;

MERGE过程的时间代价为Θ(n), 其中n=r-p+1是待合并的元素个数。

伪码：

MERGE(A, p, q, r)　　n1 ← q - p + 1　　n2 ← r - q　　create arrays L[1.. n1+1] and R[1.. n2+1]　　for i ← 1 to n1　　　　do L[i] ← A[p + i - 1]　　for j ← 1 to n2　　　　do R[j] ← A[q + j]　　L[n1 + 1] ← ∞　　R[n2 + 1] ← ∞　　i ← 1　　j ← 1　　for k ← p to r　　　　do if L[i] <= R[j]　　　　　　then 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)　　　　MERGE-SORT(A, q + 1, r)　　　　MERGE(A, p, q, r)

Java实现

public void mergeSort(int[] a, int p, int r)    {        if (p < r)        {            int q = (p + r) / 2 ;            mergeSort(a, p, q);            mergeSort(a, q + 1, r);            merge(a, p, q, r);        }    }    private void merge(int a[], int p, int q, int r)    {        int n1 = q - p + 1;        int n2 = r - q;        int[] l_array = new int[n1 + 1];        int[] r_array = new int[n2 + 1];        for (int i = 0; i < n1; i++)        {            l_array[i] = a[p + i];        }        for (int j = 0; j < n2; j++)        {            r_array[j] = a[q + j + 1];        }        l_array[n1] = Integer.MAX_VALUE;        r_array[n2] = Integer.MAX_VALUE;        int i = 0, j = 0;        for (int k = p; k <= r; k++)        {            if (l_array[i] <= r_array[j])            {                a[k] = l_array[i];                i = i + 1;            }            else            {                a[k] = r_array[j];                j = j + 1;            }        }    }