MergeSortis 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.

- If the number of items to sort is 0 or 1, return.
- Recursively sort the first and second halves separately.
- 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++]; }