C++ Program for MERGE SORT

by Arun Vishnu · Published November 28, 2008 · Updated March 28, 2009

/**************************************************************	
	Author: Arun Vishnu M V
	Web: www.arunmvishnu.com
	Description: C++ Program for MERGE SORT .
***************************************************************/
#include<conio.h>   	
#include<iostream.h>  
void m_sort(int numbers[], int temp[], int left, int right);
void merge(int numbers[], int temp[], int left, int mid, int right);

int numbers[150];
int temp[150];


int main()
{
   clrscr();
   int i,n;
   cout<<"How many numbers you want to sort: ";
   cin>>n;
   cout<<"Enter "<>numbers[i];
   //perform merge sort on array
   m_sort(numbers, temp, 0, n-1);
   cout<<"Numbers are sorted\n";
   for (i = 0; i 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);
   }
}
// Function for merge
void merge(int numbers[], int temp[], int left, int mid, int right)
{
   int i, left_end, num_elements, tmp_pos;
   left_end = mid - 1;
   tmp_pos = left;
   num_elements = right - left + 1;
   while ((left <= left_end) && (mid <= right))
   {
      if (numbers[left] <= numbers[mid])
      {
	 temp[tmp_pos] = numbers[left];
	 tmp_pos = tmp_pos + 1;
	 left = left +1;
      }
      else
      {
	 temp[tmp_pos] = numbers[mid];
	 tmp_pos = tmp_pos + 1;
	 mid = mid + 1;
      }
   }
   while (left <= left_end)
   {
      temp[tmp_pos] = numbers[left];
      left = left + 1;
      tmp_pos = tmp_pos + 1;
   }
   while (mid <= right)
   {
      temp[tmp_pos] = numbers[mid];
      mid = mid + 1;
      tmp_pos = tmp_pos + 1;
   }
   for (i=0; i <= num_elements; i++)
   {
      numbers[right] = temp[right];
      right = right - 1;
   }
}

//---------------------- END--------------------