# Merge Sort — Clean C++ Implementation & Detailed Explanation ## Introduction Merge Sort is a classic divide-and-conquer sorting algorithm with guaranteed O(n log n) time complexity. It recursively splits the array into halves, sorts each half, and merges the sorted halves. Its stability, predictable complexity, and suitability for external sorting make it an important algorithm for both interviews and production systems. The repository includes a practical C++ implementation — this blog explains how the algorithm works, walks through the code, points out potential pitfalls in the provided implementation, and provides a clean corrected version. --- ## How Merge Sort works (brief) 1. Divide: split the array into two halves. 2. Conquer: recursively sort each half. 3. Combine: merge two sorted halves into a single sorted array. Time complexity: O(n log n) for all best/average/worst cases. Space complexity: O(n) extra space is required for merging (unless in-place variants are used). --- ## Repository implementation (reference) Source: https://github.com/mashrur-rahman-fahim/algorithm/blob/main/merge.cpp. ### Observations about the repository code - The merge function uses sentinel values (INT_MAX) for convenience; this is a standard technique but requires care when working with non-integer comparisons or very large integers. - The merge_sort function in the repository attempts a multi-stage split using m, m1, m2. However, the expression int m = h + l/2; lacks parentheses and thus is parsed as h + (l / 2) — this is almost certainly a bug. The correct mid-point is int m = (l + h) / 2;. - The code uses C-style variable-length arrays int lft[s1], r[s2]. Variable-length arrays are not standard C++ (they are a GNU extension). Use vector<int> instead for portability and safety. Because of these issues, I recommend the corrected, canonical implementation shown below. --- ## Correct, idiomatic merge sort (recommended) cpp #include <bits/stdc++.h> using namespace std; void merge_vec(vector<int>& a, int l, int m, int r) { int n1 = m - l + 1; int n2 = r - m; vector<int> L(n1), R(n2); for (int i = 0; i < n1; ++i) L[i] = a[l + i]; for (int j = 0; j < n2; ++j) R[j] = a[m + 1 + j]; int i = 0, j = 0, k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) a[k++] = L[i++]; else a[k++] = R[j++]; } while (i < n1) a[k++] = L[i++]; while (j < n2) a[k++] = R[j++]; } void merge_sort(vector<int>& a, int l, int r) { if (l >= r) return; int m = l + (r - l) / 2; merge_sort(a, l, m); merge_sort(a, m + 1, r); merge_vec(a, l, m, r); } int main() { vector<int> a = {5, 2, 9, 1, 5, 6}; merge_sort(a, 0, a.size() - 1); for (int x : a) cout << x << ' '; } This corrected implementation uses vector<int> buffers (portable), correct midpoint math, and standard merging. --- ## Why the corrections matter - Midpoint calculation bug can produce wrong splits or infinite recursion in some cases. - Variable-length arrays may compile with GCC but break with other compilers (MSVC) or in strict standard mode. - Sentinels (INT_MAX) are okay but require care with integer overflow. Using explicit loops as in the corrected merge_vec avoids sentinel semantics entirely. --- ## Complexity & properties - Time: O(n log n) — splitting pays log n factor, merging costs linear time per level. - Space: O(n) extra space for merging. - Stable: yes (when using <= for merging left-first ties). - Parallelizability: easy to parallelize the two recursive sorts on large arrays. --- ## Testing & edge cases - Already-sorted and reverse-sorted arrays — algorithm still O(n log n). - Duplicate elements — stability is preserved by merging left before right when values are equal. - Very large arrays — consider iterative or external merge sort for disk-backed sorting. --- Repository: https://github.com/mashrur-rahman-fahim/algorithm/blob/main/merge.cpp Images (use in article): 1. https://www.shutterstock.com/image-photo/programmer-cyber-security-technology-male-600nw-2464110045.jpg 2. https://www.snexplores.org/wp-content/uploads/2020/11/1030_algorithm_explainer-1028x579.jpg 3. https://i0.wp.com/bdtechtalks.com/wp-content/uploads/2022/02/algorithm-formulation.jpg?ssl=1