1. Introduction
Merge sort is a classic divide-and-conquer sorting algorithm that guarantees O(n log n) time complexity in every case: best, average, and worst. It works by recursively splitting the array into two halves until each sub-array contains a single element (trivially sorted), and then merging those sub-arrays back together in sorted order. Because its performance does not degrade on already-sorted or reverse-sorted input, merge sort is widely used for sorting linked lists, external/disk-based sorting, and any scenario where predictable, consistent performance is more important than minimizing memory usage.
Cricket analogy: Merge sort is like organizing a huge squad of net bowlers into pairs, ranking each pair, then combining ranked pairs into a final bowling order — a method that takes the same predictable time whether the squad started scrambled or already in order, like the IPL auction pool.
2. Syntax
void mergeSort(int arr[], int left, int right);
void merge(int arr[], int left, int mid, int right);
/* Parameters:
arr - array of integers to sort in place
left - starting index of the current sub-array
right - ending index of the current sub-array
mid - midpoint that splits [left, right] into two halves
Initial call: mergeSort(arr, 0, n - 1); */3. Explanation
mergeSort(arr, left, right) first checks if left < right; if the sub-array has more than one element, it computes mid = left + (right - left) / 2, then recursively sorts the left half [left, mid] and the right half [mid + 1, right]. Once both halves are individually sorted, the merge() function combines them: it copies the two halves into temporary arrays, then repeatedly compares the smallest remaining elements of each temporary array and writes the smaller one back into arr, advancing whichever pointer was used. Any leftover elements from either temporary array (once the other is exhausted) are copied directly, since they are already in sorted order.
Cricket analogy: mergeSort splits a squad list at mid, sorts each half recursively, like grouping batters then bowlers separately; merge() then compares the top prospect from each temp group and picks the stronger one repeatedly, dumping any leftovers straight in since they're already ranked.
Worked trace on [38, 27, 43, 3]: split into [38, 27] and [43, 3]. [38, 27] splits into [38] and [27], which merge to [27, 38]. [43, 3] splits into [43] and [3], which merge to [3, 43]. Finally, merge [27, 38] with [3, 43]: compare 27 vs 3 -> take 3; compare 27 vs 43 -> take 27; compare 38 vs 43 -> take 38; 43 is the only element left -> take 43. Result: [3, 27, 38, 43].
Cricket analogy: Tracing [38,27,43,3] is like sorting four batters' scores: split into [38,27] and [43,3]; merge each pair to [27,38] and [3,43]; then merge those, comparing 27 vs 3, 27 vs 43, 38 vs 43, landing on the final ranked list [3,27,38,43].
4. Example
#include <stdio.h>
#include <stdlib.h>
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int *L = (int *)malloc(n1 * sizeof(int));
int *R = (int *)malloc(n2 * sizeof(int));
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];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
free(L);
free(R);
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
}
int main(void) {
int arr[] = {38, 27, 43, 3};
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
printArray(arr, n);
return 0;
}5. Output
3 27 38 436. Key Takeaways
- Time complexity is O(n log n) in the best, average, and worst case, since the array is always split evenly and merged in linear time.
- Space complexity is O(n) extra space because of the temporary L and R arrays used during merging.
- Merge sort is a stable sort (the '<=' comparison in merge preserves the order of equal elements).
- It is not an in-place algorithm in its classic form, unlike quick sort, due to the auxiliary arrays.
- It is well suited for sorting linked lists and large external datasets that don't fit in memory.
Practice what you learned
1. What is the time complexity of merge sort in the worst case?
2. What is the auxiliary space complexity of the standard merge sort implementation shown?
3. In the merge step, why is the comparison 'L[i] <= R[j]' used instead of 'L[i] < R[j]'?
4. What is the value of mid when mergeSort is called with left = 0 and right = 3?
5. Which of these is true about merge sort compared to quick sort?
Was this page helpful?
You May Also Like
Quick Sort in C
Learn quick sort in C: partition logic, pivot selection, divide-and-conquer recursion, complete code, output, and O(n log n) average complexity.
Bubble Sort in C
Master bubble sort in C: syntax, algorithm explanation, optimized code with early-exit flag, sample output, and O(n^2) complexity.
Sorting Algorithms in C
Learn bubble sort in C step by step, with an overview of selection and insertion sort and correct time complexity analysis.
Related Reading
Related Study Notes in Programming
Browse all study notesApache Spark Study Notes
Programming · 30 topics
ProgrammingApache Flink Study Notes
Programming · 30 topics
ProgrammingHadoop Study Notes
Programming · 30 topics
ProgrammingSnowflake Study Notes
Programming · 30 topics
ProgrammingApache Airflow Study Notes
Programming · 30 topics
Programmingdbt (Data Build Tool) Study Notes
Programming · 30 topics