Merge Sort Part- 3 REFERENCE : PANIMALAR ENGINEERING COLLEGE NOTES

The most common algorithm used is the merge sort. This algorithm follows divide and conquer strategy. In dividing phase the problem is divided into smaller problem and solved recursively.In conquering phase, the partitioned array is merged together recursively. Merge sort is applied to the first half and second half of the array. This gives two sorted halves which can then be recursively merged together using the merging algorithm.
The basic merging algorithm takes two input arrays A and B and an output array C. The first element of A array and B array are compared, then the smaller element is stored in the output array C and the corresponding pointer is increment. When either input array is exhausted the remainder of the other array is copied to an output array C.

void MSort (ElementType A[ ] , ElementType TmpArray[ ] , int left, int right)
{
int center;
if(left{
center = (left + right) / 2;
msort(A, TmpArray, left,center);
msort(A,TmpArray, center+1,right);
merge(A, TmpArray, left, center+1, right);
}
}

void merge(int A[ ], int TmpArray[ ], int lpos, int rpos, int rightend)
{
int i, num, leftend, tmpos;
leftend = rpos - 1;
tmpos = lpos;
num = rightend - lpos + 1;
while(lpos<=leftend) &&(rpos<=rightend)
if(A[lpos]<=A[rpos])
TmpArray[tmpos++]=A[lpos++];
else
TmpArray[tmpos++]=A[rpos++];
while(lpos<=leftend)
TmpArray[tmpos++]=A[lpos++];
while(rpos<=rightend)
TmpArray[tmpos++] = A[rpos++];
for(i=0;i<=num; i++, rightend--)
A[rightend]=TmpArray[rightend];
}

void MergeSort(ElementType A[ ], int N)
{
ElementType TmpArray[MAX];
MSort (A,TmpArray,0,N-1)
}

The merge sort algorithm is therefore easy to describe. If N-1, there is only one element to sort and the answer is at hand. Otherwise, recursively merge sort the first half and second half. This gives two sorted halves, which can then be merged together using merging algorithm.

For example to sort the eight element array 24, 23, 26, 1, 2, 27, 38, 15. We recursively sort the first four and the last four elements, obtaining 1, 13, 14, 26, 2, 15, 27, 38. Then we merge the two halves as above, obtaining the final list 1, 2, 13, 15, 24, 26, 27, 38.

Analysis of Merge Sort

                   Worst Case Analysis       --  O(NlogN)
                    Best Case Analysis         -- O(NlogN)
                    Average Case Analysis   -- O(NlogN)

Advantages of Merge Sort
It is efficient for sorting large number of elements.
It is simple than Heap sort.
It has better cache performance.
It has the advantages of worst case O(NlogN) running time.

Limitations

It requires more memory space.
It requires more processing time.