Merge Sort in C

Merge Sort in C . Merge sort is a popular sorting algorithm known for its efficiency and reliability. Merge sort follows the divide and conquer approach, breaking down the sorting task into smaller sub-problems until the base case is reached, and merging the sorted solutions to form the final sorted array. In this article, we will explore the step-by-step implementation of the Merge Sort algorithm in the C programming language.

Overview of Merge Sort Algorithm

Merge Sort operates by recursively dividing the input array into two halves until each subarray contains only one element. then it merges those sorted subarrays to produce a fully sorted array. The key steps of merge sort include-

• Divide- Split the unsorted array into half.
• Conquer- Recursively apply merge sort to each sub-array until they are reduced to a single element.
• Combine- Merge this sorted sub-array to produce the final sorted array.

Merge Sort Program in C

Lert’s write C program for implementing Merge Sort

#include <stdio.h>
// function to merge sub array
void merge(int array[], int left, int middle, int right)
{
    int i, j, k;
    int n1 = middle - left + 1;
    int n2 = right - middle;
    // creating temporary arrays
    int leftArray[n1], rightArray[n2];
    // copy data to temporary array left array and right array
    for (i = 0; i < n1; i++)
    {
        leftArray[i] = array[left + i];
    }
    for (j = 0; j < n2; j++)
    {
        rightArray[j] = array[middle + 1 + j];
    }
    // merge the temporarry array back into array
    i = 0;
    j = 0;
    k = left;
    while (i < n1 && j < n2)
    {
        if (leftArray[i] <= rightArray[j])
        {
            array[k] = leftArray[i];
            i++;
        }
        else
        {
            array[k] = rightArray[j];
            j++;
        }
        k++;
    }
    // copy the remaining elements of left array if there are any
    while (i < n1)
    {
        array[k] = leftArray[i];
        i++;
        k++;
    }
    // copying the remaining element of rigth array if there are any.
    while (j < n2)
    {
        array[k] = rightArray[j];
        j++;
        k++;
    }
}
// Recursive function to perfrom merge sort on array
void mergeSort(int array[], int left, int right)
{
    if (left < right)
    {
        int middle = left + (right - left) / 2;
        // Recursively sort the first and second half
        mergeSort(array, left, middle);
        mergeSort(array, middle + 1, right);
        // merge the sorted half
        merge(array, left, middle, right);
    }
}
void main()
{
    int array[] = {2, 5, 8, 9, 23, 25, 56, 78, 876};
    int arraysize = sizeof(array) / sizeof(array[0]);
    printf("Given array is \n");
    for (int i = 0; i < arraysize; i++)
    {
        printf("%d ", array[i]);
    }
    mergeSort(array, 0, arraysize - 1);
    printf("\nArray after sorting \n");
    for (int i = 0; i < arraysize; i++)
    {
        printf("%d ", array[i]);
    }
}

Output

In the above C program

• The merge function combines two sorted sub-arrays into a single sorted array.
• The mergeSort function recursively divides the array into two halves and calls the merge function two to merge the sorted halves.
• The main function initialize an array, calls mergeSort to sort the array, and prints the sorted array.

Merge Sort Time Complexity

Merge Sort’s time complexity is consistently effective and is expressed as O(n logn), Where n is the number of elements in the array to be sorted. The complexity of merge sort makes merge sort a reliable choice for sorting large data sets, As it maintains a relatively consistent performance regardless of input size.

Happy Coding

See Also

• C Program to Reverse a Sentence
• Identifiers in C