Here's an example of a Merge Sort implementation in C.
It divides the
array into two halves, recursively sorts them, and then merges them into
a sorted array.
Code
#include <stdio.h>
// Function to merge two subarrays
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1; // Size of left subarray
int n2 = right - mid; // Size of right subarray
// Create temporary arrays
int L[n1], R[n2];
// 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];
// Merge the temporary arrays back into the main array
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy any remaining elements of L[], if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy any remaining elements of R[], if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Function to implement merge sort
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// Recursively sort the two halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
// Function to print an array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
printArray(arr, size);
mergeSort(arr, 0, size - 1);
printf("Sorted array:\n");
printArray(arr, size);
return 0;
}
Explanation
1. Merge Function:
○ Merges two sorted subarrays into a single sorted array.
○ Handles remaining elements in either subarray if one finishes
early.
2. Recursive Merge Sort:
○ Divides the array into two halves.
○ Calls itself recursively to sort both halves.
○ Calls merge to combine the sorted halves.
3. Time Complexity:
○ Best, average, and worst case: O(nlogn)O(n \log n).
○ Space complexity: O(n)O(n) due to temporary arrays.
You can compile and run this program using any C compiler (e.g., GCC):
gcc merge_sort.c -o merge_sort
./merge_sort
Detailed Explanation of the Merge Sort Code
Merge Sort is a divide-and-conquer algorithm that breaks down the
array into smaller parts, sorts them, and merges them back in sorted
order. Let's go step-by-step through the code:
1. Merge Function
This function combines two sorted subarrays into a single sorted array.
void merge(int arr[], int left, int mid, int right) {
Variables and Temporary Arrays:
● L[n1] and R[n2]: Temporary arrays to store the left and right
halves of the main array.
● n1 and n2: Sizes of these two subarrays:
int n1 = mid - left + 1;
int n2 = right - mid;
Copying Subarrays:
● The elements from the original array are copied into the temporary
arrays L and R:
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];
Merging Subarrays:
● Compare elements from L and R, and insert the smaller value
back into the main array:
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
Remaining Elements:
● If one of the subarrays has leftover elements, copy them directly to
the main array:
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
2. Merge Sort Function
● This function divides the array into smaller subarrays, sorts them
recursively, and merges them.
void mergeSort(int arr[], int left, int right) {
if (left < right) {
Divide Step:
● Calculate the middle point of the array:
int mid = left + (right - left) / 2;
● Recursively sort the left and right halves:
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
Merge Step:
● Call the merge function to combine the sorted halves into a single
sorted array:
merge(arr, left, mid, right);
3. Print Function
● This utility function prints the elements of an array.
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
4. Main Function
● The main function demonstrates the working of merge sort.
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
printArray(arr, size);
mergeSort(arr, 0, size - 1);
printf("Sorted array:\n");
printArray(arr, size);
return 0;
}
Steps in main:
1. Define an unsorted array: {12, 11, 13, 5, 6, 7}.
2. Print the original array.
3. Call mergeSort on the entire array (left = 0, right = size
- 1).
4. Print the sorted array after sorting.
How It Works: Example Walkthrough
For the input array {12, 11, 13, 5, 6, 7}, here's how the
algorithm works:
1. Divide:
○ Split into {12, 11, 13} and {5, 6, 7}.
○ Further divide: {12, 11} and {13}, {5, 6} and {7}.
○ Continue until single-element arrays: {12}, {11}, {13},
{5}, {6}, {7}.
2. Conquer:
○ Merge {12} and {11} → {11, 12}.
○ Merge {5} and {6} → {5, 6}.
3. Combine:
○ Merge {11, 12} and {13} → {11, 12, 13}.
○ Merge {5, 6} and {7} → {5, 6, 7}.
○ Merge {11, 12, 13} and {5, 6, 7} → {5, 6, 7,
11, 12, 13}.
Time and Space Complexity
Time Complexity:
● Divide step: Takes O(logn)O(\log n) because the array is
repeatedly split in half.
● Merge step: Takes O(n)O(n) for each level of merging.
● Total: O(nlogn)O(n \log n) for all steps.
Space Complexity:
● Requires O(n)O(n) additional space for temporary arrays.
This makes Merge Sort a stable and efficient sorting algorithm for large
datasets.
