Sunday 6 October 2013

Merge Sort program in C++

#include<iostream>
using namespace std;
#include<conio.h>
template<class T>
void m_sort(T numbers[],T temp[],int left,int right);
template<class T>
void mergesort(T numbers[],T temp[],int array_size)
{
     m_sort<T>(numbers,temp,0,array_size-1);
}
template<class T>
//void merge(T numbers[],T temp[],int left,int mid,int right);
//template<class T>
void m_sort(T numbers[],T temp[],int left,int right)
{
     int mid;
     if(right>left)
     {
                   mid=(right+left)/2;
                   m_sort(numbers,temp,left,mid);
                   m_sort(numbers,temp,mid+1,right);
                   merge(numbers,temp,left,mid+1,right);
     }
}
template<class T>
void merge(T numbers[],T temp[],int left,int mid,int right)
{
     int i,left_end,num_elements,temp_pos;
         left_end=mid-1;
         temp_pos=left;
         num_elements=right-left+1;
         while((left<=left_end)&&(mid<=right))
         {
                                              if(numbers[left]<=numbers[mid])//(kept -numbers instead )
                                              {
                                                                              temp[temp_pos]=numbers[left];
                                                                              temp_pos++;
                                                                              left++;
                                              }
                                              else
                                              {
                                                                              temp[temp_pos]=numbers[mid];
                                                                              temp_pos++;
                                                                              mid++;
                                              }
         }
         while(left<=left_end)
         {
                               temp[temp_pos]=numbers[left];
                               left++;
                               temp_pos++;
         }
         while(mid<=right)
         {
                          temp[temp_pos]=numbers[mid];
                          mid++;
                          temp_pos++;
         }
         for(i=0;i<=num_elements;i++)
         {
                                     numbers[right]=temp[right];
                                     right--;
         }
}
int main()
{
    int a[20],b[20],n;
    cout<<"\n enter the value of n:";
    cin>>n;
    cout<<"\nenter n elements:";
    for(int i=0;i<n;i++)
    {
                    cin>>a[i];
     }   
    mergesort(a,b,n);
    cout<<"\n sorted elements are :";
    for(int i=0;i<n;i++)
    {
                    cout<<"\t"<<a[i]<<"\t";
    }
    _getch();
    return 0;
}

                              
     
     
     

No comments:

Post a Comment