Merge Sort in C Language
Merge sort is a popular divide-and-conquer sorting algorithm that recursively divides the input array into two halves, sorts each half, and then merges the sorted halves back together. In C language, an implementation of the Merge Sort algorithm can be as follows:
#include <stdio.h>
#include <stdlib.h>
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; /* initial index of first subarray */
j = 0; /* initial index of second subarray */
k = l; /* initial index of merged subarray */
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++;
}
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2; // middle index
/* sort first and second halves */
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
/* merge the sorted halves */
merge(arr, l, m, r);
}
}
int main() {
int arr[] = { 12, 11, 13, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
The merge
function takes an integer array arr
and three integer values l
, m
, and r
. It merges two sorted sub-arrays arr[l..m]
and arr[m+1..r]
into a single sorted sub-array arr[l..r]
.
The mergeSort
function recursively sorts the array by dividing it into two halves, sorting each half, and then merging them back together using the merge
function.
The main
function creates an integer array and calls the mergeSort
function to sort it. Finally, it prints the sorted array to the console.
Note that the worst-case time complexity of merge sort is O(n log n), which makes it very efficient for sorting large arrays. However, it has a higher overhead than other algorithms like insertion sort or selection sort for small arrays.