MERGE SORT

Conceptually, a merge sort works as follows

1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
2. Repeatedly merge sublists to produce new sublists until there is only 1 sublist remaining. This will be the sorted list.

The following figures will clearly illustrate the working of merge sort:-

IMPLEMENTATION OF MERGE SORT USING LINKED LIST

Here each number, that the user is prompted to input is stored in a node of the linked list, and then the list is divided, and then a recursive function is called to implement the merging.

/***********************************************************************************************************///MERGE SORT

//SORTING A LINK LIST

//RECURSIVE DEFINITION

#include<stdio.h>

#include<conio.h>

struct Node

{

int val;

struct Node*next;

};

typedef struct Node node;

void printlist(node*);

node*makenode(int);

node*mergesort(node*);

node*divide(node*);

node*merge(node*,node*);

int main()

{

int i,tmp;

node*start,*nn,*last;

clrscr();

start=last=NULL;

while(1)

{

printf("enter the data part of the node:");

scanf("%d",&tmp);

if(tmp==0)

break;

nn=makenode(tmp);

if(start)

{

last->next=nn;

last=nn;

}

else

{

start=last=nn;

}

}

start=mergesort(start);

printlist(start);

getch();

return 1;

}

node*mergesort(node*start)

{

node*nh;

if(start&&start->next)

{

nh=divide(start);

start=mergesort(start);

nh=mergesort(nh);

start=merge(start,nh);

}

return start;

}

node*divide(node*start)

{

node*ptr1,*ptr2,*start2=NULL;

if(start->next)

{

ptr1=start;

ptr2=start->next->next;

while(ptr2)

{

ptr1=ptr1->next;

ptr2=ptr2->next;

if(ptr2)

ptr2=ptr2->next;

}

start2=ptr1->next;

ptr1->next=NULL;

}

return start2;

}

node*merge(node*s1,node*s2)

{

node*s3,*l3,*tmp;

s3=l3=NULL;

while(s1&&s2)

{

if(s1->val<s2->val)

{

tmp=s1;

s1=s1->next;

}

else

{

tmp=s2;

s2=s2->next;

}

if(!s3)

s3=tmp;

else

l3->next=tmp;

l3=tmp;

}

if(s1)

{

if(!s3)

s3=s1;

else

l3->next=s1;

}

if(s2)

{

if(!s3)

s3=s2;

else

l3->next=s2;

}

return s3;

}

void printlist(node*start)

{

while(start)

{

printf("%d\t",start->val);

start=start->next;

}

}

node*makenode(int tmp)

{

node*nn;

nn=(node*)malloc(sizeof(node));

nn->val=tmp;

nn->next=NULL;

return nn;

}

/*******************************************************************************/

IMPLEMENTATION OF MERGE-SORT USING ARRAYS

/*****************************************************************************/

//MERGE SORT

#include<stdio.h>

#include<conio.h>

void mergesort(int*,int ,int);

void merge(int *,int ,int);

//int b[20];

int main()

{

//clrscr();

int arr[20];

int i,j,n;

clrscr();

printf("ENTER THE NUMBER OF ELEMENTS OF ARRAY:");

scanf("%d",&n);

printf("enter the data of array:\n");

for(i=0;i<n;i++)

scanf("%d",&arr[i]);

mergesort(arr,0,n-1);

for(i=0;i<n;i++)

printf("%d\t",arr[i]);

getch();

return 1;

}

void mergesort(int *arr,int i,int j)

{

int mid;

if(i>=j)

return;

else

{

mid=(i+j)/2;

mergesort(arr,i,mid);

mergesort(arr,mid+1,j);

merge(arr,i,j);

}

}

void merge(int *arr,int i,int j)

{

int start=i;

int mid,k,l=i,b[20];

mid=(i+j)/2;

k=mid+1;

while(k<=j&&i<=mid)

{

if(arr[i]<arr[k])

b[l++]=arr[i++];

else

b[l++] =arr[k++];

}

if(i>mid)

while(k<=j)

b[l++]=arr[k++];

else if(k>j)

while(i<=mid)

b[l++]=arr[i++];

for(l=start;l<=j;l++)

arr[l]=b[l];

}

/****************************************************************************/