Mergesort
MERGESORT(A,p,r) sorts the elements in the subarray A[p..r]
If p>=r, the subarray has at most one element and is therefore already sorted. Otherwise the divide step calculates an index q that partitions A[p…r] into two subarrays containing ?n/2? elements and A[q+1 …r] containing ?n/2? elements.
MERGESORT(A,0,n-1) sorts the array A of length n