Implement merge sort |Data Structure in C|

Introduction

     Merge Sort is a powerful sorting algorithm known for its efficiency and stability. In this blog post, we will explore a C program that implements the Merge Sort algorithm. By breaking down the code into key functions, we'll delve into the divide-and-conquer strategy, demonstrating how Merge Sort elegantly sorts an array.  

Code

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

    void msort(int[], int, int, int);
    void partition(int[], int, int);

    void main() {
        int a[15], i, s;
        clrscr();

        // Input: Total number of elements
        printf("Enter total number of elements: ");
        scanf("%d", &s);

        // Input: Elements of the array
        printf("Enter the elements:\n");
        for(i = 0; i < s; i++) {
            scanf("%d", &a[i]);
        }

        // Sorting using Merge Sort
        partition(a, 0, s - 1);

        // Output: Sorted array after Merge Sort
        printf("After Merge Sort:\n");
        for(i = 0; i < s; i++) {
            printf("%d\t", a[i]);
        }

        getch();
    }

    void partition(int a[], int low, int high) {
        int mid;
        if(low < high) {
            mid = (low + high) / 2;
            partition(a, low, mid);
            partition(a, mid + 1, high);
            msort(a, low, mid, high);
        }
    }

    void msort(int a[], int low, int mid, int high) {
        int i, mi, k, l, temp[55];
        l = low;
        i = low;
        mi = mid + 1;

        while((l <= mid) && (mi <= high)) {
            if(a[l] <= a[mi]) {
                temp[i] = a[l];
                l++;
            } else {
                temp[i] = a[mi];
                mi++;
            }
            i++;
        }

        if(l > mid) {
            for(k = mi; k <= high; k++) {
                temp[i] = a[k];
                i++;
            }
        } else {
            for(k = l; k <= mid; k++) {
                temp[i] = a[k];
                i++;
            }
        }

        for(k = low; k <= high; k++) {
            a[k] = temp[k];
        }
    }
       
     

Output

    Enter total number of elements: 6
    Enter the elements:
    34 12 56 78 32 10
    After Merge Sort:
    10      12      32      34      56      78
       

Explanation

1. Header Files:

The program includes the standard input/output header <stdio.h> and the console I/O header <conio.h>.

2. Function Prototypes:

Function prototypes for msort (Merge Sort) and partition are declared to organize the code structure.

3. Main Function:

The main function serves as the program's entry point.

Users input the total number of elements and the array elements.

4. Merge Sort Algorithm:

The program utilizes the partition function to recursively divide the array into sub-arrays.

The msort function merges the sorted sub-arrays back together.

5. Output:

The program displays the sorted array after the Merge Sort operation.

Conclusion

     Merge Sort is a divide-and-conquer algorithm that elegantly sorts arrays, ensuring efficiency and stability. This C program demonstrates the step-by-step implementation of Merge Sort, offering insights into its recursive and merging mechanisms. Feel free to run the program with different arrays and observe how Merge Sort efficiently organizes elements in ascending order. This example serves as a valuable introduction to the principles of Merge Sort in programming. Happy coding!