MergeSort.c

// Algo: MergeSort(A,l,r)
// Input: array A[l..r]
// Output: permuted array A[l..r] that is sorted in increasing order
if l<r then
	m = ⌊(l+r)/2⌋;
	MergeSort(A,l,m);
	MergeSort(A,m+1,r);
	// Watch out: Merge is not the same as MergeSort 
	Merge(A,l,r,m);
  
// Algo: Merge(A,l,r,m)
// Input: array A; indexes l, r and m from MergeSort
// Output: A[l..r] is sorted in increasing order

// first two lines copy the initial array to the secondary B array
// whereby the order for the first half is the same
// and the order in the second half (in B) is swapped
for i = l to m do B[i] = A[i];
for i = m+1 to r do B[r+m-i+1] = A[i];

// we compare the two arrays and fill in the numbers in the correct ordering
// if the numbers are the same, we take the one from the right side
i = l; j = r;
for k = l to r do
	if B[i]<B[j] then A[k] = B[i]; i = i+1;
	else A[k] = B[j]; j = j-1;