Data Structure and Algorithm

/********************************************************************
--------------------------------------
ALGORITHM FOR MERGE SORT
--------------------------------------
mergesort(data,first,last)
1)if first < last
a)find middle as mid = (first + last) / 2
b)mergesort(data,first,mid)
c)mergesort(data,mid + 1,last);
d)merge(data,first,last)

merge(array1,first,last)
1)mid = (first + last) / 2
2)set i = first, j = mid + 1 and k = 0
3)while both left and right subarrays of array1 contain elements
a)if array1[i] < array1[j]
   temp[k++] = array1[i++]
b)else, temp[k++] = array1[j++]
4)Load into temp the remaining elements of array 1
5)load to array1 the content of temp

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

#include "iostream.h"
#include "conio.h"

void merge(int *,int,int,int);

void mergesort(int *data,int first,int last)
{
int mid;
if(first < last) //If more than one element
  {
   mid = (first + last) / 2; //Find mid
   mergesort(data,first,mid); //Sort Left Subarray
   mergesort(data,mid + 1,last); //Sort Right Subarray
   merge(data,first,mid,last); //Merge Left and Right Subarray
  }
}

void merge(int *data,int first,int mid,int last)
{
int i,j,k;
i = first;
j = mid + 1;
k = 0;
int *temp = new int[last - first + 2];
while(i <= mid && j <= last) //While the end of Left or Right Subarray
  {
   //Compare data and save to temporary array
   if(data[i] < data[j])
    temp[k++] = data[i++];
   else
    temp[k++] = data[j++];
  }

if(i <= mid) //If more items in Left Subarray
  for(j = i;j <= mid;j++) //Copy items to temp
   temp[k++] = data[j];
else //more items in Right Subarray
  for(i = j;i <= last;i++)
   temp[k++] = data[i];

k = 0;
for(i = first;i <= last;i++) //Copy items from temporary array to original array
  data[i] = temp[k++];
}

int main()
{
int n,*arr;
clrscr();
cout << "How many Numbers? ";
cin >> n;
arr = new int[n];
cout << "\nEnter Elements : ";
for(int i = 0;i < n;i++) //Scan Inputs
  cin >> arr[i];

mergesort(arr,0,n - 1); //Sort
cout << endl << "\nSorted : ";
for(int i = 0;i < n;i++)
  cout << arr[i] << ' ';

getch();
return 0;
}

OUTPUT

How many numbers? 10

Enter Elements : 25 65 47 88 64 10 -98 0 35 6

Sorted : -98 0 6 10 25 35 47 64 65 88

Download Original File

Merge.cpp