Merge Sort in C: Program to Sort Array Using Merge Sort Algorithm

Introduction

In this tutorial, we will learn how to write a C program to sort an array using the merge sort algorithm.

Merge sort is a highly efficient, comparison-based sorting algorithm that follows the divide-and-conquer paradigm. It works by dividing the array into two halves, recursively sorting each half, and then merging the sorted halves back together.

Merge sort is used in various real-world applications, such as:

• Large Datasets: Efficiently sorts large arrays with predictable performance
• External Sorting: Used in external sorting algorithms for large files
• Stable Sorting: Maintains relative order of equal elements
• Parallel Processing: Can be easily parallelized for multi-core systems

Visual Example

Let's see how merge sort sorts the array [38, 27, 43, 3, 9, 82, 10]:

[38, 27, 43, 3, 9, 82, 10]
[38, 27, 43]  [3, 9, 82, 10]
[38] [27, 43]  [3, 9] [82, 10]
[38] [27] [43]  [3] [9] [82] [10]

[38] [27] [43]  [3] [9] [82] [10]
[27, 38] [43]  [3, 9] [10, 82]
[27, 38, 43]  [3, 9, 10, 82]
[3, 9, 10, 27, 38, 43, 82]

C Program for Merge Sort

#include <stdio.h>

// Function to merge two subarrays
void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    // Create temporary arrays
    int leftArr[n1], rightArr[n2];
    
    // Copy data to temporary arrays
    for(i = 0; i < n1; i++)
        leftArr[i] = arr[left + i];
    for(j = 0; j < n2; j++)
        rightArr[j] = arr[mid + 1 + j];
    
    // Merge the temporary arrays back into arr[]
    i = 0;
    j = 0;
    k = left;
    while(i < n1 && j < n2) {
        if(leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }
    
    // Copy remaining elements of leftArr[]
    while(i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }
    
    // Copy remaining elements of rightArr[]
    while(j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

// Function to perform merge sort
void mergeSort(int arr[], int left, int right) {
    if(left < right) {
        int mid = left + (right - left) / 2;
        
        // Recursively sort first and second halves
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        
        // Merge the sorted halves
        merge(arr, left, mid, right);
    }
}

int main() {
    int n, i;
    
    // Ask user for number of elements
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    
    // Declare array
    int arr[n];
    
    // Read elements into the array
    printf("Enter %d elements:\n", n);
    for(i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    // Perform merge sort
    mergeSort(arr, 0, n - 1);
    
    // Display sorted array
    printf("\nSorted array in ascending order: ");
    for(i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

Sample Output

Enter the number of elements: 7
Enter 7 elements:
38 27 43 3 9 82 10

Sorted array in ascending order: 3 9 10 27 38 43 82

Another Example:

Enter the number of elements: 6
Enter 6 elements:
12 11 13 5 6 7

Sorted array in ascending order: 5 6 7 11 12 13

Example with Negative Numbers:

Enter the number of elements: 6
Enter 6 elements:
-5 10 -2 8 0 -10

Sorted array in ascending order: -10 -5 -2 0 8 10

Program Explanation

Let's break down the code step by step:

1. Include Header File: #include <stdio.h> includes the standard input/output library.
2. merge() Function:
   • Merges two sorted subarrays: arr[left...mid] and arr[mid+1...right]
   • Creates temporary arrays leftArr and rightArr
   • Compares elements and merges them in sorted order
3. mergeSort() Function:
   • Recursively divides the array into two halves
   • Calls itself on the left and right halves
   • Merges the sorted halves using the merge() function
4. main() Function:
   • Gets user input for the array
   • Calls mergeSort(arr, 0, n-1) to sort the array
   • Prints the sorted array

Merge Sort Algorithm

Step-by-step algorithm:

1. Start
2. Read the array elements
3. If left < right:
   • Find the middle index: mid = left + (right - left) / 2
   • Recursively sort the left half: mergeSort(arr, left, mid)
   • Recursively sort the right half: mergeSort(arr, mid + 1, right)
   • Merge the two sorted halves: merge(arr, left, mid, right)
4. Print the sorted array
5. End

Time and Space Complexity

// Change the comparison in the merge function
if(leftArr[i] >= rightArr[j]) {  // Change <= to >= for descending
    arr[k] = leftArr[i];
    i++;
} else {
    arr[k] = rightArr[j];
    j++;
}

Frequently Asked Questions

Previous Topic: -->> Insertion Sort in C   ||   Next topic: -->> Quick Sort in C