Answer to Question #273270 in C for Amit

Question

Implement merge sort.

Answer 1

#include <stdio.h>
#include <stdlib.h>
void merge(int array1[], int l, int m, int r)
{
	int i, j, k;
	int n1 = m - l + 1;
	int n2 = r - m;
	int L[n1], R[n2];
	for (i = 0; i < n1; i++)
		L[i] = array1[l + i];
	for (j = 0; j < n2; j++)
		R[j] = array1[m + 1 + j];


	i = 0; 
	j = 0; 
	k = l; 
	while (i < n1 && j < n2) {
		if (L[i] <= R[j]) {
			array1[k] = L[i];
			i++;
		}
		else {
			array1[k] = R[j];
			j++;
		}
		k++;
	}


	while (i < n1) {
		array1[k] = L[i];
		i++;
		k++;
	}


	while (j < n2) {
		array1[k] = R[j];
		j++;
		k++;
	}
}


void mergeSort(int array1[], int l, int r)
{
	if (l < r) {
		int m = l + (r - l) / 2;
		mergeSort(array1, l, m);
		mergeSort(array1, m + 1, r);


		merge(array1, l, m, r);
	}
}


void display(int array1[], int n)
{
	int i;
	for (i = 0; i < n; i++)
		printf("%d ", array1[i]);
	printf("\n");
}


int main()
{
	int array1[] = { 21,25,23,45,64,34,27,45,67,87,77 };
	int n = sizeof(array1) / sizeof(array1[0]);


	printf("Array elements before sorting \n");
	display(array1, n);


	mergeSort(array1, 0, n - 1);


	printf("\nArray elements after sorting \n");
	display(array1, n);
	return 0;
}