Detailed Explanation of Merge Sort Implementation in C

Merge Sort is an efficient sorting algorithm based on the “Divide and Conquer” method. Its core idea is to break down a large problem into multiple smaller problems, solve the smaller problems, and then merge the results to obtain the overall solution.

Basic Principles of Merge Sort

1. Decomposition Continuously divide the array to be sorted until each sub-array contains only one element (a single element is considered sorted by default).
2. Merging Merge two sorted sub-arrays into a larger sorted array.
3. Recursion Repeat the above process until all sub-arrays are merged into a complete sorted array.

Implementation Code

The implementation of Merge Sort consists of two parts: the recursive function<span>mergeSort</span> for dividing the array, and the<span>merge</span> function for merging two sorted arrays.Header File

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

Main Function

int main() {    int arr[] = { 12, 11, 13, 5, 6, 7 };    int arr_size = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: ");    printArray(arr, arr_size);
    mergeSort(arr, 0, arr_size - 1);
    printf("Sorted array: ");    printArray(arr, arr_size);
    return 0;}

Sorting Main Function

// Merge Sort Main Function
// arr: Array to be sorted
// left: Starting index
// right: Ending index
void mergeSort(int arr[], int left, int right) {    if (left < right) {        // Calculate the middle index to avoid overflow        int 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 parts        merge(arr, left, mid, right);    }}

The main function includes a merge function, and the code for the merge function is as follows:

// Merge two sorted sub-arrays
// arr: Original array
// left: Starting index of the left sub-array
// mid: Middle index (ending index of the left sub-array)
// right: Ending index of the right sub-array
void merge(int arr[], int left, int mid, int right) {    // First part, save the contents of the arr array
    // Save into two arrays, left and right L, R
    int n1 = mid - left + 1;  // Length of the left sub-array
    int n2 = right - mid;     // Length of the right sub-array
    // Create temporary arrays to store the left and right sub-arrays
    int* L = (int*)malloc(n1 * sizeof(int));    int* R = (int*)malloc(n2 * sizeof(int));    int i, j;
    // Copy data to temporary arrays
    for (i = 0; i < n1; i++)    {        L[i] = arr[left + i];    }    for (j = 0; j < n2; j++)    {        R[j] = arr[mid + 1 + j];    }
    // Second part, merge the two arrays
    // Merge the temporary arrays back into the original array
    i = 0;      // Starting index of the left sub-array
    j = 0;      // Starting index of the right sub-array
    int k = left;   // Starting index of the merged array
    while (i < n1 && j < n2)     {        // Place the smaller element
        if (L[i] <= R[j])         {            arr[k] = L[i];            i++;        }        else         {            arr[k] = R[j];            j++;        }        k++;    }
    // Third part, the while loop ends when one array is fully traversed
    // The other array may still have elements, either left or right
    // Copy remaining elements of the left sub-array
    while (i < n1)     {        arr[k] = L[i];        i++;        k++;    }
    // Copy remaining elements of the right sub-array
    while (j < n2)     {        arr[k] = R[j];        j++;        k++;    }
    // Free the temporary array memory
    free(L);    free(R);}

Print Array Interface

void printArray(int arr[], int size) {    for (int i = 0; i < size; i++)        printf("%d ", arr[i]);    printf("\n");}

Code Analysis

merge Function:

• Function: Merges two sorted sub-arrays (<span>arr[left..mid]</span> and <span>arr[mid+1..right]</span>) into a sorted array
• Implementation Steps:

1. Create temporary arrays to store the left and right sub-arrays
2. Compare the elements of the two sub-arrays and place them in the original array in ascending order
3. 
4. Copy remaining elements to the original array
5. Free the temporary array memory

mergeSort Function:

• Function: Recursively divides and sorts the array
• Implementation Steps:

1. Calculate the middle index<span>mid</span> to divide the array into left and right parts
2. Recursively sort the left and right halves
3. Call the <span>merge</span> function to merge the sorted parts

Characteristics of Merge Sort

• Advantages
• Stable time complexity: Regardless of the input data, the time complexity isO(n log n)
• Stable sorting algorithm: The relative position of equal elements remains unchanged
• Suitable for handling large-scale data, much more efficient than bubble, selection, and insertion sort
• Disadvantages
• Requires additional memory space (O(n)) to store temporary arrays
• For small-scale data, the overhead of recursive calls may make it less efficient than insertion sort

Applicable Scenarios

• Sorting large-scale data
• Scenarios requiring stable sorting algorithms
• External sorting (when data cannot be fully loaded into memory)

Summary Merge Sort is far more efficient than bubble, selection, and insertion sort, but its efficiency comes at the cost of memory overhead. Choose Merge Sort for sorting large data volumes.