Merge Sort

Input: A[], p, r, where p < r.

Merge-Sort(A, p, r)
{
if ( p < r )
{
q = [(p + r)/2];
Merge-Sort(A, p, q);
Merge-Sort(A, q, r);
Merge(A, p, q, r);
}
}

Megre(A, p, q, r)
{
n1 = q - p + 1;
n2 = r - q;
for (i = 0; i <= n1; i++)
L[i] = A [p+i];
for (j = 0; j <= n2; j++)
R[j] = A[q+j];
L[n1 +1] = Sentinel;
R[n2 +1] = Sentinel;
i = j = 0;
for (k = p; k <= r; k++)
{
if (L[i] <= R[j])
{
A[k] = L[i];
i++;
}
else
{
A[k] = R[j];
j++;
}
}
}

Features:
1. loop invariant
2. stable
3. T(n) = O(nlgn)