C Exercises: Merge sort algorithm

Last update on December 20 2024 13:08:31 (UTC/GMT +8 hours)

Write a C program to sort a list of elements using the merge sort algorithm.
Note: Merge sort is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output.

Visual presentation - Merge search algorithm:

C programming Merge sort algorithm

Sample Solution:

Sample C Code:

#include<stdio.h>
// Function to merge the two halves arra[l..m] and arra[m+1..r] of array arra[]
void merge(int arra[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    // Create temporary arrays L[] and R[]
    int L[n1], R[n2];
    // Copy data to temp arrays L[] and R[]
    for(i = 0; i < n1; i++)
        L[i] = arra[l + i];
    for(j = 0; j < n2; j++)
        R[j] = arra[m + 1 + j];
    i = 0;
    j = 0;
    k = l;
    // Merge the two halves back into arra[l..r]
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arra[k] = L[i];
            i++;
        } else {
            arra[k] = R[j];
            j++;
        }
        k++;
    }
    // Copy the remaining elements of L[], if there are any
    while (i < n1) {
        arra[k] = L[i];
        i++;
        k++;
    }
    // Copy the remaining elements of R[], if there are any
    while (j < n2) {
        arra[k] = R[j];
        j++;
        k++;
    }
}
// Function to perform merge sort on array arra[] from index l to r
void mergeSort(int arra[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2; // Calculate the middle index to divide the array
        mergeSort(arra, l, m);   // Recursive call on the left subarray
        mergeSort(arra, m + 1, r); // Recursive call on the right subarray
        merge(arra, l, m, r);      // Merge the two halves
    }
}
// Function to print an array
void print_array(int A[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}
// Main function to test mergeSort
int main() {
    int arra[] = {125, 181, 130, 25, 61, 887};
    int arr_size = sizeof(arra) / sizeof(arra[0]);
    // Print the original array
    printf("Given array is \n");
    print_array(arra, arr_size);
    // Perform merge sort on the array
    mergeSort(arra, 0, arr_size - 1);

    // Print the sorted array
    printf("\nSorted array is \n");
    print_array(arra, arr_size);
    return 0;
}

Sample Output:

Given array is                                                                                                
125 181 130 25 61 887                                                                                         
                                                                                                              
Sorted array is                                                                                               
25 61 125 130 181 887

Flowchart:

C Programming Code Editor:

Previous: Write a C program to sort a list of elements using the insertion sort algorithm.
Next: Write a C program to sort numbers using heap algorithm(MAX heap).