### MergeSort

MergeSort is an efficient sorting technique that is fairly easy to implement. In terms of speed, `MergeSort` is considerably faster than the simple sorting techniques.

A downside to `MergeSort` is that it requires an additional array in memory, equal in size to the one being sorted.

The "guts" of `MergeSort` is the merging of two already sorted arrays. Merging two sorted arrays A and B creates a third array, C, that contains all of the elements of A and B, also arranged in sorted order.

The idea behind `MergeSort` is to divide an array in half, sort each half, and them use a "merge" function to merge the two halves into a single sorted array.

1. If the number of items to sort is 0 or 1, return.
2. Recursively sort the first and second halves separately.
3. Merge the two sorted halves into a sorted group.

Merge sort is example of a "divide-an-conquer" algorithm: divide into two equal-sized sets, and conquer by merging the two sorted sets into one.

`MergeSort` pseudo-code:

```   mergeSort(T a[], T tmpA[], int left, int right)

if (left == right)  return;
mid = (left + right) / 2;
mergeSort(a, tmpA, left, mid);
mergeSort(a, tmpA, mid+1, right);

for (i = left; i <= right; i++) tmpA[i] = a[i];
i1 = left, i2 = mid + 1;

for (int cur_i = left;  cur_i <= right; cur_i++) {
if (i1 == mid + 1)
a[cur_i] = tmpA[i2++];
else if (i2 > right)
a[cur_i] = tmpA[i1++];
else if (tmpA[i1] < tmpA[i2])
a[cur_i] = tmpA[i1++];
else
a[cur_i] = tmpA[i2++];
}
```