Merge Sort

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

int a[100];
int temp[100];

void merge_sort(int a[], int temp[], int n);
void m_sort(int a[], int temp[], int left, int right);
void merge(int a[], int temp[], int left, int mid, int right);

int main(void)
{
	int i,n;
	clrscr();
	printf("How many elements?\n");
	scanf("%d",&n);
	printf("\nEnter integers into the array.\n");
	for(i=0;i<n;++i)
		scanf("%d",&a[i]);
	printf("\nArray before sorting as follows:\n");
	for(i=0;i<n;++i)
		printf("%d\t",a[i]);
	merge_sort(a,temp,n);
	printf("\n\nArray after sorting as follows:\n");
	for(i=0;i<n;++i)
		printf("%d\t",a[i]);
	getch();
	return 0;
}

void merge_sort(int a[], int temp[], int n)
{
	m_sort(a,temp,0,n-1);
}

void m_sort(int a[], int temp[], int left, int right)
{
	int mid;
	if(right>left)
	{
		mid=(right+left)/2;
		m_sort(a,temp,left,mid);
		m_sort(a,temp,mid+1,right);
		merge(a,temp,left,mid+1,right);
	}
}

void merge(int a[],int temp[], int left, int mid, int right)
{
	int i,left_end,n,temp_pos;
	left_end=mid-1;
	temp_pos=left;
	n=right-left+1;
	while((left<=left_end)&&(mid<=right))
	{
		if(a[left]<=a[mid])
		{
			temp[temp_pos]=a[left];
			temp_pos++;
			left++;
		}
		else
		{
			temp[temp_pos]=a[mid];
			temp_pos++;
			mid++;
		}
	}
	while(left<=left_end)
	{
		temp[temp_pos]=a[left];
		temp_pos++;
		left++;
	}
	while(mid<=right)
	{
		temp[temp_pos]=a[mid];
		mid++;
		temp_pos++;
	}
	for(i=0;i<n;++i)
	{
		a[right]=temp[right];
		right--;
	}
}

Related posts:

Leave a Reply

Your email address will not be published. Required fields are marked *