Implementation of Merge Sort in C Programming Language

Merge Sort is one of the most efficient and widely used sorting algorithms. It follows the divide-and-conquer approach, which means it breaks down a problem into smaller subproblems, solves them, and then combines the results. Merge Sort is particularly useful because it guarantees a time complexity of O(n log n) in all cases, making it a reliable choice for sorting large datasets.

In this article, we will explore how Merge Sort works, implement it in C, and understand the implementation with special attention to memory management and C-specific considerations.

How Merge Sort Works

Merge Sort works by recursively dividing the input array into smaller subarrays until each subarray contains only one element. Then, it keeps merging these subarrays in a sorted order. Here’s a step-by-step breakdown:

  1. Divide: Split the array into two halves.
  2. Conquer: Recursively sort each half.
  3. Combine: Merge the two sorted halves into a single sorted array.

Refer to these articles for better understanding on how merge sort algorithm works:

Implementation of Merge Sort Algorithm in C

Here’s the implementation of Merge Sort Algorithm in C with detailed memory management:


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

/**
 * Merges two sorted subarrays into a single sorted array.
 * 
 * @param arr   Pointer to the array containing the two subarrays to be merged
 * @param left  The starting index of the first subarray
 * @param mid   The ending index of the first subarray
 * @param right The ending index of the second subarray
 * @return      0 on success, -1 on memory allocation failure
 */
int merge(int* arr, int left, int mid, int right) {
  /* Calculate the sizes of the two subarrays */
  int n1 = mid - left + 1;  /* Size of the left subarray */
  int n2 = right - mid;     /* Size of the right subarray */

  /* Dynamically allocate memory for temporary arrays */
  int* L = (int*)malloc(n1 * sizeof(int));
  int* R = (int*)malloc(n2 * sizeof(int));
  
  /* Check if memory allocation was successful */
  if (L == NULL || R == NULL) {
    /* Free any allocated memory before returning */
    free(L);
    free(R);
    return -1;  /* Return error code */
  }

  /* Copy data to temporary arrays */
  for (int i = 0; i < n1; i++)
    L[i] = arr[left + i];
  for (int j = 0; j < n2; j++)
    R[j] = arr[mid + 1 + j];

  /* Initialize indices for the subarrays and the main array */
  int i = 0;      /* Index for the left subarray (L) */
  int j = 0;      /* Index for the right subarray (R) */
  int k = left;   /* Index for the main array (arr) */

  /* Merge the two subarrays back into the main array */
  while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
      /* If the current element in L is smaller, add it to the main array */
      arr[k] = L[i];
      i++;
    } else {
      /* If the current element in R is smaller, add it to the main array */
      arr[k] = R[j];
      j++;
    }
    k++;
  }

  /* Copy any remaining elements from the left subarray (if any) */
  while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
  }

  /* Copy any remaining elements from the right subarray (if any) */
  while (j < n2) {
    arr[k] = R[j];
    j++;
    k++;
  }

  /* Free the dynamically allocated memory */
  free(L);
  free(R);
  
  return 0;  /* Return success code */
}

/**
 * Recursively sorts the array using the merge sort algorithm.
 * 
 * @param arr   Pointer to the array to be sorted
 * @param left  The starting index of the array segment to be sorted
 * @param right The ending index of the array segment to be sorted
 * @return      0 on success, -1 on memory allocation failure
 */
int merge_sort(int* arr, int left, int right) {
  if (left < right) {
    /* Find the middle point to divide the array into two halves */
    int mid = left + (right - left) / 2;  /* Avoid potential integer overflow */
    
    /* Recursively sort the left half of the array */
    int result = merge_sort(arr, left, mid);
    if (result != 0) return result;
    
    /* Recursively sort the right half of the array */
    result = merge_sort(arr, mid + 1, right);
    if (result != 0) return result;
    
    /* Merge the two sorted halves */
    return merge(arr, left, mid, right);
  }
  
  return 0;  /* Return success code */
}

/**
 * Helper function to print an array
 */
void print_array(const int* arr, int size) {
  printf("[");
  for (int i = 0; i < size; i++) {
    printf("%d", arr[i]);
    if (i < size - 1) printf(", ");
  }
  printf("]");
}

/* Example usage */
int main() {
  /* Define the array to be sorted */
  int arr[] = {4, 1, 2, 3};
  int size = sizeof(arr) / sizeof(arr[0]);
  
  /* Print the original array */
  printf("Original array: ");
  print_array(arr, size);
  printf("\n");
  
  /* Call the merge_sort function to sort the array */
  int result = merge_sort(arr, 0, size - 1);
  
  /* Check if sorting was successful */
  if (result == 0) {
    /* Print the sorted array */
    printf("Sorted array: ");
    print_array(arr, size);
    printf("\n");
  } else {
    printf("Error: Memory allocation failed during sorting\n");
  }
  
  return result;
}

Detailed Explanation of the Implementation

Let’s break down the merge sort implementation step by step to understand how it works.

The merge_sort Function

The merge_sort function is the main function that performs the sorting. It takes three parameters:

  1. arr: The array to be sorted.
  2. left: The starting index of the segment of the array to be sorted.
  3. right: The ending index of the segment of the array to be sorted.

Here’s how it works:

  1. Base Condition: The function first checks if left < right. This condition ensures that the array has more than one element. If left is not less than right, it means the array has either one or zero elements, and no sorting is needed.
  2. Divide the Array: If the array has more than one element, the function calculates the middle index (mid) using the formula (left + right) // 2. This divides the array into two halves.
  3. Recursive Calls: The function then calls itself recursively to sort the left half (merge_sort(arr, left, mid)) and the right half (merge_sort(arr, mid + 1, right)). This process continues until the array is divided into single-element subarrays.
  4. Merge the Sorted Halves: Once the two halves are sorted, the merge function is called to merge them back into a single sorted array.

Key C-specific aspects:

  1. Pointer Usage: The array is passed as a pointer to its first element.
  2. Integer Overflow Prevention: Middle index calculation uses left + (right - left) / 2 instead of (left + right) / 2 to prevent potential integer overflow.
  3. Error Propagation: The function checks return values from recursive calls and the merge function.

The merge Function

The merge function is responsible for merging two sorted subarrays into a single sorted array. It takes four parameters:

  1. arr: The array containing the two subarrays to be merged.
  2. left: The starting index of the first subarray.
  3. mid: The ending index of the first subarray.
  4. right: The ending index of the second subarray.

Here’s how it works:

  1. Calculate Subarray Sizes: The sizes of the two subarrays are calculated using n1 = mid - left + 1 (size of the left subarray) and n2 = right - mid (size of the right subarray).

  2. Create Temporary Arrays: Two temporary arrays, L and R, are created to hold the elements of the left and right subarrays, respectively.

  3. Merge Process: The function then merges the two subarrays back into the main array (arr). It uses three indices:

    • i: Index for the left subarray (L).
    • j: Index for the right subarray (R).
    • k: Index for the main array (arr).

    The function compares the elements of L and R one by one. The smaller element is placed into the main array, and the corresponding index (i or j) is incremented. This process continues until all elements from either L or R are placed into the main array.

  4. Copy Remaining Elements: If there are any remaining elements in L or R, they are copied directly into the main array.

Memory Management

  • We use malloc() to allocate memory for temporary arrays L and R in the merge function.
  • The size of allocation is calculated using sizeof(int) to ensure portability across different platforms.
  • We perform null checks after allocation to handle potential memory allocation failures.
  • Memory is explicitly freed using free() before the function returns.

Example Run

Let’s walk through an example with the array [4, 1, 2, 3]:

  1. The merge_sort function is called with left = 0 and right = 3.
  2. The array is divided into two halves: [4, 1] and [2, 3].
  3. Each half is further divided and sorted recursively:
    • [4, 1] becomes [4] and [1], which are merged into [1, 4].
    • [2, 3] becomes [2] and [3], which are merged into [2, 3].
  4. Finally, the two sorted halves [1, 4] and [2, 3] are merged into the final sorted array [1, 2, 3, 4].
  5. All temporary memory is freed after each merge operation.

Memory Complexity

  1. Stack Space: O(log n) due to recursive calls
  2. Heap Space: O(n) for temporary arrays during merging
  3. Total Space: O(n)

The implementation includes proper error handling and memory management, which are crucial aspects of C programming. Each memory allocation is checked for success, and resources are properly freed to prevent memory leaks.

Implementation in other Languages