• Recursive algorithm.
• Runs in O(NlogN) time.

Basic idea: If we have two sorted arrays, we can merge them in linear time
with N comparisons only. Given an array to be sorted, we can consider separately
its left half and its right half, sort them and then merge them.

Where is the recursion?

1. Merging two sorted arrays:

Array A: 3, 7, 10, 15
Array B: 1, 4, 8, 9, 20
Array C: (merged)


1, 3, 4, 7, 8, 9, 10, 15, 20
2. Mergesorting an array:

The following figure gives the state of the array at each step of the mergesort algorithm.
Each splitting is indicated in blue, each merging - in purple.
Parts merged at some previous step are in gray.

mergesort( int [] a, int left, int right)
{
	if (right > left)
	{
		middle = left + (right - left)/2;
		mergesort(a, left, middle);
		mergesort(a, middle+1, right);
		merge(a, left, middle, right);
	}
}	

Assumption: N is a power of two.

For N = 1: time is a constant (denoted by 1)

Otherwise: time to mergesort N elements = time to mergesort N/2 elements plus
time to merge two arrays each N/2 elements.

Time to merge two arrays each N/2 elements is linear, i.e. N

Thus we have:

Next we will solve this recurrence relation. First we divide (2) by N:

N is a power of two, so we can write

Now we add equations (3) through (8) : the sum of their left-hand sides
will be equal to the sum of their right-hand sides:

After crossing the equal term, we get

T(1) is 1, hence we obtain

Hence the complexity of the MergeSort algorithm is O(NlogN).