The

** Mergesort(A,p,r){**
**
if p < r**
**
then q <- |(p+ r)/2|**
**
Mergesort(A,p,q)**
**
Mergesort(A,q+1,r)**
**
Merge(A,p,q,r)**
** }**

** **To sort the entire sequence
A, Mergesort(A,1,length[A]) is called where length[A]=N.

Mergesort works by splitting the list into two halves and then sorting each half recursively. Mergesort may be considered to be a tree based algorithm and over here it is executed in a depth first manner. For the above list the algorithm starts by handling the merging of elements as follows (the trend in which the sublists are being considered):

1. First, elements 1 and 2
are handled.

2. Then, elements from 0 through
2 are handled (note the black items indicating the border elements).

3. Then, elements 3 and 4
are handled. After this, elements 5 and 6.

4. Then, elements 3 through
6 are handled.

Subsequently, elements 0 through 6 are handled and so on until elements 0 to 14 are handled.

The Merge algorithm takes two
sorted lists and merges them to give a sorted list. It assumes the existence
of a temporary merge space whose current contents are shown on the upper
canvas of the above applet. Mereg takes the the smaller of the first elements
of the two lists and places it into the merge space. When either input
list is exhausted, the remainder of the other list is copied to the merge
space. The sorted sublist is then copied back from the merge space into
the appropriate indices.

Merge Sort algorithm uses the process of merging two sorted lists recursively to accomplish the sorting of an unsorted list. Firstly, two sorted lists of length M and N respectively can be merged in O(M+N) time. If the lists have the same size N then the time will be O(2*N) or O(N).

First, each individual element of the list is considered as a 1-element sorted list. The merge algorithm is then used N/2 times to merge pairs of elements into sorted lists of length 2. This will produce N/2 sorted lists each of length 2. It takes N/2 comparisons to accomplish this. Pairs of 2-element lists are then merged to produce N/4 sorted lists each of length 4. In this case there are N/4 merge operations each taking at most 4 comparisons. This process continues until we have two sorted lists of size N/2 and we merge them in O(N) time. There are log(N) levels of merging. Hence, Merge Sort has a worst-case complexity of O(N*log(N)).