Write a C program for Marge Sort.

Algorithm
MergeSort(A,p,r):

	if p < r
  q = ⌊ (p+r)/2 ⌋
	 MergeSort(A,p,q)
	 MergeSort(A,q+1,r)
	 Merge(A,p,q,r)

Merge(A,p,q,r):

	n1 = q - p + 1
	n2 = r - q
	let L, R be new arrays
	for i = 1 to n1
	 L[i] = A[p+i-1]
	for j = 1 to n2
	 R[j] = A[q+j]
	L[n1+1] = ∞
	R[n2+1] = ∞
	i = 1
	j = 1
	for k = p to r
	 if L[i] ≤ R[j]
	 A[k] = L[i]
	 i = i + 1
	 else
	 A[k] = R[j]
	 j = j + 1

Figure: Marge Sort
C Programming Code

#include <stdio.h>

void merge_sort(int i, int j, int a[], int aux[]) {
    if (j <= i) {
        return;
    }
    int mid = (i + j) / 2;

    merge_sort(i, mid, a, aux);
    merge_sort(mid + 1, j, a, aux);
    int pointer_left = i;
    int pointer_right = mid + 1;
    int k;

    for (k = i; k <= j; k++) {
        if (pointer_left == mid + 1) {
            aux[k] = a[pointer_right];
            pointer_right++;
        } else if (pointer_right == j + 1) {
            aux[k] = a[pointer_left];
            pointer_left++;
        } else if (a[pointer_left] < a[pointer_right]) {
            aux[k] = a[pointer_left];
            pointer_left++;
        } else {
            aux[k] = a[pointer_right];
            pointer_right++;
        }
    }

    for (k = i; k <= j; k++) {
        a[k] = aux[k];
    }
}

int main() {
    //!showSort(a)
    int a[5], aux[5], n, i;
    printf("Enter number of elements in the array:\n");
    scanf("%d", &n);
    printf("Enter %d integers\n", n);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);

    merge_sort(0, n - 1, a, aux);

    printf("Printing the sorted array:\n");
    for (i = 0; i < n; i++)
        printf("\t%d", a[i]);

    return 0;
}

Output

Enter number of elements in the array:
5
Enter 5 integers
5
4
3
2
1
Printing the sorted array:
	1	2	3	4	5

Unknown's avatar

Published by Md. Anisur Rahman

I am Md. Anisur Rahman. I have completed Cyber Security for MSCSE at United International University in 2022.I have completed PGDIT from IIT, Jahangirnagar University in 2020. I'm a Head of IT at Programming24 School.

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.