Merge Sort in C Programming

In this source code example, we will write a code to implement the Merge Sort algorithm in the C programming language.

The merge sort algorithm is a comparison-based method that was invented by John Von Neumann. Each element in the adjacent list is compared for sorting. The performance of the algorithm is in the order of O(n log n). This algorithm is the best algorithm for sorting a linked list.

Merge Sort in C Programming

In this C program, we will take input from the User or console. Let's write a C program to sort N numbers in ascending order using the Merge Sort algorithm:
#include<stdio.h>

void Mergesort(int[], int, int);
void Merge(int[], int, int, int);

void main() {
	int x[20], i, n;
	printf("\n Enter the no of element to be sorted:");
	scanf("%d", &n);
	printf("\n Enter %d elements:", n);
	for (i = 0; i < n; i++)
		scanf("%d", &x[i]);
	Mergesort(x, 0, n - 1);
	printf("\n The sorted array is:\n");
	for (i = 0; i < n; i++)
		printf("%4d", x[i]);
}

void Mergesort(int a[], int p, int r) {
	int q;
	if (p < r) {
		q = (p + r) / 2;
		Mergesort(a, p, q);
		Mergesort(a, q + 1, r);
		Merge(a, p, q, r);
	}
}

void Merge(int a[], int p, int q, int r) {
	int b[20], l1, r1, i;
	l1 = p;
	r1 = q + 1;
	i = p;
	while ((l1 <= q) && (r1 <= r)) {
		if (a[l1] < a[r1]) {
			b[i] = a[l1];
			l1 = l1 + 1;
			i = i + 1;
		} else {
			b[i] = a[r1];
			r1 = r1 + 1;
			i = i + 1;
		}
	}
	while (l1 <= q) {
		b[i] = a[l1];
		l1 = l1 + 1;
		i = i + 1;
	}
	while (r1 <= r) {
		b[i] = a[r1];
		r1 = r1 + 1;
		i = i + 1;
	}
	for (i = p; i <= r; i++)
		a[i] = b[i];
}

Output:


 Enter the no of element to be sorted: 5

 Enter 5 elements:
50
10
20
30
40

 The sorted array is:
  10  20  30  40  50

Related Algorithms in C Programming


Comments