C Program: Merge Sort in Ascending Order

1. Introduction

Merge Sort is a divide-and-conquer sorting algorithm that divides the unsorted list into n sublists, each containing one element, and then repeatedly merges these sublists to produce new sorted sublists until there's only one sublist remaining. The merging process orders the values while combining them, ensuring a sorted list as a result.

2. Program Overview

The program structure is:

1. merge: A function to merge two halves of an array.

2. mergeSort: The main function that sorts the array using the Merge Sort algorithm.

3. printArray: A utility function to display the contents of the array.

4. main: The primary function where program execution begins.

3. Code Program

#include <stdio.h>
#include <stdlib.h>

// Merges two subarrays of arr[].
void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    // create temp arrays
    int L[n1], R[n2];

    // Copy data to temp arrays L[] and R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // Merge the temp arrays back into arr[l..r]
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy the remaining elements of L[], if there are any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy the remaining elements of R[], if there are any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Main function that sorts arr[l..r] using merge()
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // Same as (l+r)/2, but avoids overflow for large l and r
        int m = l + (r - l) / 2;

        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

// Utility function to display the array's content
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Main function to test the mergeSort function
int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("Sorted array is \n");
    printArray(arr, arr_size);
    return 0;
}

Output:

Given array is
38 27 43 3 9 82 10
Sorted array is
3 9 10 27 38 43 82

4. Step By Step Explanation

1. The mergeSort function divides the array into two halves, sorts them and then merges the sorted halves using the merge function.

2. The merge function is a key process that assumes the sub-arrays arr[l..m] and arr[m+1..r] are sorted and merges them to produce a single sorted sub-array.

3. The division of the array into two halves is performed recursively until each sub-array contains a single element.

4. Merging starts from the smallest unit (i.e., two single elements) and proceeds to create larger sorted arrays, eventually leading to the sorted array of n elements.

The logic behind the mergeSort is to divide the problem into smaller instances until they can be easily solved and then combine the solutions to solve the original problem.