Tag Archives: mergesort c code

Merge Sort

Merge Sort  belongs to category of divide and conquer algorithms. Which means it divides the problem into  small subproblems, solves them and then combine the solutions of these subproblems to generate solution  of the original problem.Merge Sort compares elements with each other for sorting the list.

The steps followed to mergesort are are:

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

 For more information on merge sort visit http://en.wikipedia.org/wiki/Merge_sort

Below is the C++ code for merge sort algorithm.
CODE:

/*
 http://randomtechbits.in/
*Program to sort numbers using MERGESORT
*inputs: N- number of integers to sort ,A-array of integers       
*output: sorted array of integers 
*code tested on devc++ IDE
*/
#include
#include
using namespace std;

void merge(int A[],int p,int q,int r,int O[])
{
int i=p;
int j=q+1;
int k=p;
//Note that I have intionally used few extra lines in all of the follwing loops tomake it more clear to learners
while((i<=q)&&(j<=r))
  {
  if(A[i]<A[j])
    {
    O[k++]=A[i++];
    }
  else
    {
     O[k++]=A[j++];
    }
}
while(i<=q)
  {
  O[k++] =A[i++];
  }
while(j<=r)
  {
  O[k++]=A[j++];
  }
int l=p;
while(l<=r)
  {
  A[l]=O[l];
  l=l+1;
  }
}

void mergesort(int A[],int p,int r,int O[])
{
  if( p < r)
    {
    int q=(p+r)/2;
    mergesort(A,p,q,O);
    mergesort(A,q+1,r,O) ;
    merge(A,p,q,r,O);
    }
}

main()
{
int N,temp;
int *A,*O;
int i,j;
cout<<"Enter the number of elements in array:\n"; cin>>N;
A=new int[N];
O=new int[N];
cout<<"Enter the array\n";
for(i=0;i<N;i++)   cin>>A[i];
mergesort(A,0,N-1,O);
cout<<"\nThe Sorted array after MERGE SORT:"<<i<<"\n";  
for(i=0;i<N;i++)
  cout<<"\t"<<A[i];
//for more codes visit Code Library

getch(); 
}