C++ Program Code for Merge Sort Algorithm implementation on an array, using template class

/*The following C++ Program code is to implement merge sort algorithm of array sorting. The user is asked first to enter the number of element in the array & then he also enters the elements in that array. The merge sorting algorithm is applied on that array & the sorted array is displayed */

#include<iostream>
#include<stdlib.h>
using namespace std;

template<class T>
void m_sort(T nos[],T t[],int l,int r);


template<class T>
void mergesort(T nos[],T t[],int asize)
{
     m_sort<T>(nos,t,0,asize-1);
}


template<class T>
void m_sort(T nos[],T t[],int l,int r)
{
     int mid;
     if(r>l)
     {
                   mid=(r+l)/2;
                   m_sort(nos,t,l,mid);
                   m_sort(nos,t,mid+1,r);
                   merge(nos,t,l,mid+1,r);
     }
}


template<class T>
void merge(T nos[],T t[],int l,int mid,int r)
{
     int i,l_end,num_elements,t_pos;
         l_end=mid-1;
         t_pos=l;
         num_elements=r-l+1;
         while((l<=l_end)&&(mid<=r))
         {
                                              if(nos[l]<=nos[mid])//(kept -nos instead )
                                              {
                                                                              t[t_pos]=nos[l];
                                                                              t_pos++;
                                                                              l++;
                                              }
                                              else
                                              {
                                                                              t[t_pos]=nos[mid];
                                                                              t_pos++;
                                                                              mid++;
                                              }
         }
         while(l<=l_end)
         {
                               t[t_pos]=nos[l];
                               l++;
                               t_pos++;
         }
         while(mid<=r)
         {
                          t[t_pos]=nos[mid];
                          mid++;
                          t_pos++;
         }
         for(i=0;i<=num_elements;i++)
         {
                                     nos[r]=t[r];
                                     r--;
         }
}


int main()
{
    int a[20],b[20],n;
    cout<<"\nEnter The Total Number Of Elements:";
    cin>>n;
    cout<<"\nEnter "<<n<<" elements (Use Spacebar as separator) : ";
    for(int i=0;i<n;i++)
    {
                    cin>>a[i];
    } 

    mergesort(a,b,n);

    cout<<"\nThe sorted element list is \n";
    for(int i=0;i<n;i++)
    {
                    cout<<a[i]<<"\t";
    }

    system("pause");
    return 0;
}

Screenshot:

Read More...

C program for merge sorting, using linked list: Creating two linked lists & merge them using Merge sort.

#include<stdio.h>                                           //for standard input/output functions
#include<conio.h>                                          //for console input/output functions

struct node
{
int info;
struct node *next;
}*front = NULL,*front1=NULL,*front2=NULL;      //creating 3 node's pointer variable
 //with initial value NULL, as empty list
 
void insert()                                                             //Function to insert the list item,  
{
struct node *t,*q;
int item;
t = (struct node *)malloc(sizeof(struct node));   //To reserve the memory space to node's element
 printf("Input the item value to be added in the queue : ");
scanf("%d",&item);                                            //user inputs the integer data
 t->info = item;
if( front == NULL )                                              //If the list is still empty
 {
front=t;
front->next=NULL;
}
else                                                                         //If the list is not empty 
{
q = front;
while( q->next!= NULL )
q=q->next;
t->next = q->next;
q->next = t;
}
}

void insert1()                      //Function to insert the list item,
{
struct node *t,*q;
int item;
t = (struct node *)malloc(sizeof(struct node)); //To reserve the memory space to node's element
printf("Input the item value to be added in the queue : ");
scanf("%d",&item);                                         //user inputs the integer data
t->info = item;
if( front == NULL )                                           //if the list is empty
 {
front=t;
front->next=NULL;
}
else                                                                     //if the list is not empty 
{
q = front;
while( q->next!= NULL )
q=q->next;
t->next = q->next;
q->next = t;
}
}

void m1_sort(struct node *t)          //for internal use in function m_sort()
 { 
struct node *tt;
tt=front2;
while(tt!=NULL)
tt=tt->next;
tt->next=t;
}

void m_sort()                                   //for sorting the list & merging
 {
struct node *t1,*t,*temp,*tt;
t=front;
t1=front1;
while(t!=NULL||t1!=NULL)         //for traversing the list till the occurrence of NULL element  
{
if((t->info)<(t1->info))
{
temp=(struct node*)malloc(sizeof(struct node));
temp->info=t->info;
temp->next=NULL;
if(front2==NULL)
front2=temp;
else
{
tt=front2;
while(tt!=NULL)
tt=tt->next;
tt->next=temp;
}
}
else
{
temp=(struct node*)malloc(sizeof(struct node));
temp->info=t1->info;
temp->next=NULL;
if(front2==NULL)
front2=temp;
else
{
tt=front2;
while(tt!=NULL)
tt=tt->next;
tt->next=temp;
}
}
t=t->next;
t1=t1->next;
}
if(t1!=NULL)
m1_sort(t1);
else if(t!=NULL)
m1_sort(t);
}


void display()                          //to display the list element 
{
struct node *ptr;
ptr = front2;
if(front == NULL)
printf("Queue is empty\n");
else
{ 
printf("Queue is :\n");
printf("Priority Item\n");
while(ptr != NULL)
{
printf("%5d\n",ptr->info);
ptr = ptr->next;
}
}
}


int main()
{
int ch;
while(ch!=4)
{
printf("1.Insert in 1st queue\n");
printf("2.Insert in 2nd queue\n");
printf("3.Display\n");
printf("4. Sort!!\n");
printf("5.Quit\n");
printf("Enter your choice : ");
scanf("%d", &ch);                       //asking the user choice of the list operation
switch(ch)
{
case 1:
insert();
break;
case 2:
insert1();
break;
case 3:
display();
break;
case 4:
m_sort();
break;
case 5:
exit(1);
default :
printf("Wrong choice\n");
}
}
getche();                                     //for exit the program after a keystroke
return 0;
}

Read More...