mergeSort.c

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

void merge(int arr[], int l, int m, int r)
{
	int i, j, k;
	int n1 = m - l + 1;
	int n2 = r - m;

	// Create temp arrays
	int leftArray[n1], rightArray[n2];

	// Copy data to temp arrays
	// leftArray[] and rightArray[]
	for (int i = 0; i < n1; i++)
		leftArray[i] = arr[l + i];
	for (int j = 0; j < n2; j++)
		rightArray[j] = arr[m + 1 + j];

	
	i = 0 , j=0 , k=l;
	while (i < n1 && j < n2) {
		if (leftArray[i] < rightArray[j]) arr[k] = leftArray[i++];
		else arr[k] = rightArray[j++];
		k++;
	}

	// Copy the remaining elements
	// of leftArray[], if there are any
	while (i < n1) arr[k++] = leftArray[i++];

	// Copy the remaining elements of
	// rightArray[], if there are any
	while (j < n2) arr[k++] = rightArray[j++];
}

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

		// Sort first and second halves
		mergeSort(arr, l, m);
		mergeSort(arr, m + 1, r);

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

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


int main()
{
	int arr[] = {87, 76, 90, 1, 309, 101, 2, 56};
	int arr_size = sizeof(arr) / sizeof(arr[0]);

	printf("Given array is \n");
	printArray(arr, arr_size);

	mergeSort(arr, 0, arr_size - 1);

	printf("\nSorted array is \n");
	printArray(arr, arr_size);
	return 0;
}