anirudhjain75
9/29/2015 - 6:03 PM

merge_sort_implementation.cpp

#include <iostream>
#include <vector>
#include <conio.h>
#include <stdio.h>
#include <cmath>
using namespace std;
std::vector<int> merge(vector<int> arr,vector<int> arr1,vector<int> arr2)
{
	for(int i = 0;i<arr1.size();)
		for(int j = 0;j<arr2.size();)
			for(int k = 0;k<arr.size();k++)
				{
					if(arr1[i]<arr2[j])
						{
							arr[k]=arr1[i];
							i++;
						}
					else if(arr1[i]>arr2[j])
						{
							arr[k]=arr2[j];
							j++;
						}
					}
return arr;
}
int main()
{
	int n,m;
	scanf("%u", &n);
	m=(n+1)/2;
	vector<int> arr(n);
	vector<int> arr1(m+1);
	vector<int> arr2(m+1);
	for (int i = 0;i < n;i++)
		scanf("%u", &arr[i]);
	//if(n%2==0)
	for (int t = 0; t < m; t++)
	{
		arr1[t]=arr[t];
	}
	/*else(n%2==1)
		for (int t = 0; t < (n+1)/2; t++)
		{
			arr1[t]=arr[t];
		}*/
	for (int i = 0; i < m-1; i++)
		for (int j = 1; j < m; j++)
		{
			if(arr1[j]<arr1[i])
			{
				int p=arr1[j];
				arr1[j]=arr1[i];
				arr1[i]=p;
			}
		}
	for(int z=m;z<(2*m);z++)
	{
		arr2[z]=arr[z];
	}
	for (int i = m; i < (2*m)-1 ; i++)
		for(int j=m+1;j<(2*m);j++)
		{
			if(arr2[j]<arr2[i])
			{
				int p=arr2[j];
				arr2[j]=arr2[i];
				arr2[i]=p;
			}
		}
	printf("%u",merge(arr,arr1,arr2));
	for (int j = 0;j < n;j++)
		printf("%u\n", arr[j]);
	for (int j = 0;j < m;j++)
		printf("%u\n", arr1[j]);
	int d;
	if (n%2==0)
		for (int j = m;j < (2*m);j++)
			printf("%u\n", arr2[j]);
	else
		for (int j = m+1;j < (2*m);j++)
			printf("%u\n", arr2[j]);
	return 0;
}