Wednesday, September 19, 2018

Merge Sort Program in C++

//MERGE SORT PROGRAM IN C++

#include<iostream>
using namespace std;

void merge(int arr[], int start, int size, int mid)
{
int s1, s2, i, j;

//Assigning size to the two array to be merged.
s1 = mid - start + 1;
s2 = size - mid;

int arr1[s1], arr2[s2];

//Initailizing those array
for (i = 0; i < s1; i++)
arr1[i] = arr[start + i];
for (j = 0; j < s2; j++)
arr2[j] = arr[mid + 1 + j];
i = 0;
j = 0;

int k = start;

//Merging them in sorted array
while (i < s1 && j < s2)
{
if (arr1[i] <= arr2[j])
{
arr[k] = arr1[i];
i++;
}
else
{
arr[k] = arr2[j];
j++;
}
k++;
}

while (i < s1)
{
arr[k] = arr1[i];
i++;
k++;
}

while (j < s2)
{
arr[k] = arr2[j];
j++;
k++;
}
}

void mergesort(int arr[],int start, int size)
{
int mid;

if (size - start + 1 < 2)
{
return;
}

else
{
mid = (start + size)/2;
//Sorting left array
mergesort(arr, start, mid);
//Sorting right array
mergesort(arr, mid + 1,size);
merge(arr, start, size, mid);
}
}

int main()
{
int arr[10], size;
cout<<"\n Enter the size of array : ";
cin>>size;
cout<<"\n Enter the element in the array : ";
for (int i = 0; i < size; i++)
cin>>arr[i];

mergesort(arr, 0, size-1);
cout<<"\n Sorted Array is : ";
for (int i = 0; i < size; i++)
cout<<arr[i]<<" ";
return 0;
}

No comments:

Post a Comment