Example: merge sort

Recurrence : T(n) ? 2 . T(n/2) + c1 . n + c2

T(1) = c3

T(n) = O(n log n)

mergeSort(A, i, j) // sort A[i,...j]

{

if (i==j) return A[];

mergeSort(A, i, (i+j)/2);

mergeSort(A, (i+j)/2 + 1, j);

merge(A, i, (i+j)/2, j)

}

merge(A, i, k, j)

//PreCond: A[i,...,k] and A[k,...,j] are sorted

//PostCond:A[i,...,j] is sorted