This type of sorting follows the divide and rule policy. This algorithm divides the array of n elements into n separate arrays of size 1 (each array contains one element) and then rejoins the divided arrays one by one with each other to form the array of size n.

To explain this sorting technique we take an array ar[] containing s elements.

Two variables “upper” and “lower” stores the upper limit (position of last element, generally s-1) and the lower limit (position of first element, generally 0) of the array respectively. The middle position of the array is obtained by adding upper and lower and dividing the result by 2.

The obtained position is used to divide the array into two sub arrays. The procedure is followed repeatedly on the sub arrays and the subsequent sub arrays until upper equals lower (this happens when each sub array contains one element each, i.e. when the array has been divided into s sub arrays).

This process can be better explained with an example:

Let an array ar[] contain the following elements:

`34 45 89 23 38 76 12 28`

The length of the array is 8, so s=8. Thus lower=0 (since position of elements in array starts from 0) and upper=s-1=7.

Thus the array will be split from the middle, i.e. (0+7)/2=3 (element at 4th position). The array becomes:

`[34 45 89 23] [38 76 12 28]  ([] represents a sub array)`

Now each sub array will be considered an individual array and the procedure will be applied to each sub array again.

The left sub array has four elements and so, lower=0 and upper=3. Thus middle point occurs at 1 (position of second element)

The right sub array also has four elements and so, lower=4 and upper=7. Thus the middle point occurs at 5 (position of 6th element)

Thus the sub arrays get divided and the result becomes:

`[34 45] [89 23] [38 76] [12 28]`

This process is repeated till all sub arrays contain 1 element each.

`[34] [45] [89] [23] [38] [76] [12] [28] `

The s divided arrays are joined together to form the complete array and the elements are sorted at the same time. This is done by sorting the elements of two arrays while joining them in a third array.

This process can be better explained with an example:

Let us take the divided array shown above:

`[34] [45] [89] [23] [38] [76] [12] [28] ([] indicate a separate array)`

The combining procedure takes place as follows:

The single array obtained at the end is the sorted array.

The mergesort algorithm generally contains two distinct methods:

mergesort(ar[],lower,upper):This method shares its name with the sorting technique and is generally used to split the array of n elements into n sub arrays each containing 1 element. This is done by using a recursive function for most convenience.

An algorithm for the method is as follows:

```mergesort(ar[],lower, upper)
/* this method takes three arguments: the array pointer ar[],
the lower limit of the array(the position of the first element)
and the upper limit of the array (the position of the last element) */

int mid; //stores the position of middle element

if(upper>lower)
{

mid=(lower+upper)/2; //calculates middle position

mergesort(ar,lower,mid); // recursively splits the left subarray
mergesort(ar,mid+1,upper); // recursively splits the right subarray

merge(ar,lower,mid,mid+1,upper);// merges the separated arrays

}
```

merge(ar[],lower,mid,mid+1,upper):This method joins the two separated arrays into a temporary array before transferring the elements to the original array. The method also sorts the array while joining them.

Let us consider an array ar[] with s elements. Let us also consider that the array has been split into two sub arrays at the middle position.

The array ar[] has been sent to the merge() method along with the position of the first element and the position of the last element of both the sub arrays. Two variables p and q(initialized to the position of the first element of first sub array and second sub array respectively) are used to point to the elements in the arrays.

Now the elements in the two sub arrays are put into a third temporary array D[] in the following manner:

• The element at p and q are compared.
• If element at p matches the condition, the element is put into D and p is incremented by 1.
• If element at q matches the condition, the element is put into D and q is incremented by 1.
• This is continued till either p or q reaches the last element in its array.
• If p reaches its end, the remaining elements in the array pointed by q is put in D[] or vice versa.

(The condition refers to elements being greater or lesser than each other.)

After all the elements in the sub arrays have been sorted in D[], the elements are put back into the sub arrays in the order it is present in D[].

Let us take an example to better understand this method:

Let an array ar[] have 8 elements:

`23 34 45 89 12 28 38 76`

Let it be split up into two sub arrays:

Left sub array: [23 34 45 89]
Right sub array: [12 28 38 76]

p will point to the beginning of left sub array while q will point to the beginning of the second sub array.

The elements will be stored in D[] in the following manner:(considering ar[p]

``` P			     q				D
[23	34	45	89] [12	   28	  38	76]*	[]

P			     	   q			D
[23	34	45	89] [12	   28	  38	76]	[12]

P			     	   q			D
[23	34	45	89] [12	   28	  38	76]*	[12]

P			   q			D
[23	34	45	89] [12	   28	  38	76]	[12 23]

P			   q			D
[23	34	45	89] [12	   28	  38	76]*	[12 23]

P			      	  q		D
[23	34	45	89] [12	   28	  38	76]	[12 23 28]

P			     	  q		D
[23	34	45	89] [12	   28	  38	76]*	[12 23 28]

P			  q		D
[23	34	45	89] [12	   28	  38	76]	[12 23 28 34]

P			  q		D
[23	34	45	89] [12	   28	  38	76]*	[12 23 28 34]

P			      	q	D
[23	34	45	89] [12	   28	  38	76]	[12 23 28 34 38]

P			     	q	D
[23	34	45	89] [12	   28	  38	76]*	[12 23 28 34 38]

P			q	D
[23	34	45	89] [12	   28	  38	76]	[12 23 28 34 38 45]

P			q	D
[23	34	45	89] [12	   28	  38	76]*	[12 23 28 34 38 45]

P			q	D
[23	34	45	89] [12	   28	  38	76]	[12 23 28 34 38 45 76]

* indicates elements being pointed by p and q are being compared

```

Since q reaches limit, the remaining element of p is transferred to D[]. Thus the elements of D[] are:

`[12 23 28 34 38 45 76 89]`

These elements are put into the sub arrays in the order it is present in D[].

An algorithm for this method is as follows:

```merge(ar[], lower1, upper1, lower2, upper2)
/*the arguments include: the array pointer ar[],
the position of first element of the left sub array,
the position of last element of the left sub array,
the position of first element of the right sub array,
the position of last element of the right sub array */

int p,q,n,j,D[100];

p=lower1;
q=lower2;

n=0; // position counter for D[]

while((p<=upper1)&&(q<=upper2))

/* conditionally placing elements in D[] */
D[n++]=(ar[p]<ar[q]?ar[p++]:ar[q++]);

while(p<=upper1)
// placing remaining elements of sub array pointed by p in D[]
D[n++]=ar[p++];

while(q<=upper2)
// placing remaining elements of sub array pointed by p in D[]
D[n++]=ar[q++];

n=0;
for(p=lower1;p<=upper1;p++,n++)
// placing elements from D[] to left sub array
ar[p]=D[n];

for(q=lower2,j=n;q<=upper2;q++,j++)
// placing elements from D[] to right sub array
ar[q]=D[j];

```

Mergesort may be done using array or linked list. Fully working codes of mergesort using array and linked list has been given below. The programs have been written in C.

Mergesort using array:

```#include<stdio.h>
#include<conio.h>
void merge(int ar[],int lower1,int upper1,int lower2,int upper2)
{
int p,q,n,j,D[100];
p=lower1;
q=lower2;
n=0;
while((p<=upper1)&&(q<=upper2))
{
D[n++]=(ar[p]<ar[q]?ar[p++]:ar[q++]);
}
while(p<=upper1)
{
D[n++]=ar[p++];
}
while(q<=upper2)
{
D[n++]=ar[q++];
}
n=0;
for(p=lower1;p<=upper1;p++,n++)
{
ar[p]=D[n];
}
for(q=lower2,j=n;q<=upper2;q++,j++)
{
ar[q]=D[j];
}
}
void mergesort(int ar[],int lower,int upper)
{
int mid;
if(upper>lower)
{
mid=(lower+upper)/2;
mergesort(ar,lower,mid);
mergesort(ar,mid+1,upper);
merge(ar,lower,mid,mid+1,upper);
}
}
int main (int argc, char *argv[])
{
clrscr();
int ar[100],s,i,lower,upper;
printf("\nEnter the size of the array: ");
scanf("%d",&s);
printf("\nEnter the elements of the array:");
for(i=0;i<s;i++)
{
scanf("%d",&ar[i]);
}
lower=0;
upper=s-1;
mergesort(ar,lower,upper);
printf("\nThe sorted array is:");
for(i=0;i<s;i++)
{
printf("\n%d",ar[i]);
}

getch();
}

```

```#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<stdlib.h>
{
int data;
};
{
return n;
}
int getans()
{
int i;
printf("\n Press 1 to continue and 0 to quit");
scanf("%d",&i);
return i;
}
{
printf("\n Enter the value:");
scanf("%d",&(n->data));
n->next=NULL;
}
{
while(n!=NULL)
{
printf("\n %d",n->data);
n=n->next;
}

}
{
{
}
{
}
{
}
else
{
}
}
{
{
}
{
}
}
int main (int argc, char *argv[])
{
clrscr();
while(getans())
{
node->next=getnode();
node=node->next;
putdata(node);
}