📖 Merge Sort: A Divide-and-Conquer algorithm that splits the array into HALVES recursively until each piece has just 1 element, then MERGES pairs back together in sorted order.
C++ Implementation:
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1, n2 = right - mid;
int L[n1], R[n2];
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++];
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid); // sort left half
mergeSort(arr, mid + 1, right); // sort right half
merge(arr, left, mid, right); // merge both halves
}
}
Worked Dry-Run — Array: [38, 27, 43, 3, 9, 82, 10]:
DIVIDE (split until single elements):
[38,27,43,3,9,82,10]
↓ split
[38,27,43,3] [9,82,10]
↓ split ↓ split
[38,27] [43,3] [9,82] [10]
↓ ↓ ↓
[38][27] [43][3] [9][82] [10]
CONQUER (merge back in sorted order):
[38][27] → [27,38]
[43][3] → [3,43]
[27,38] + [3,43] → [3,27,38,43]
[9][82] → [9,82]
[9,82] + [10] → [9,10,82]
FINAL MERGE:
[3,27,38,43] + [9,10,82] → [3,9,10,27,38,43,82]
PYQ-Style Example — Array with a Negative Number: [17, 9, 13, 55, -2, 8, 40, 3]:
DIVIDE:
[17,9,13,55,-2,8,40,3]
↓ split
[17,9,13,55] [-2,8,40,3]
↓ split ↓ split
[17,9] [13,55] [-2,8] [40,3]
↓ ↓ ↓ ↓
[17][9] [13][55] [-2][8] [40][3]
CONQUER (merge back — negative numbers compare normally, -2 is smallest):
[17][9] → [9,17]
[13][55] → [13,55]
[9,17]+[13,55] → [9,13,17,55]
[-2][8] → [-2,8]
[40][3] → [3,40]
[-2,8]+[3,40] → [-2,3,8,40]
FINAL MERGE:
[9,13,17,55] + [-2,3,8,40] → [-2,3,8,9,13,17,40,55]
💡 Key Point: Merge Sort's comparison logic (L[i] <= R[j]) works identically for negative numbers — no special handling needed, since -2 < 3 is evaluated the same way as any other comparison.
| Case | Time Complexity |
|---|
| Best / Average / Worst | O(n log n) — ALWAYS, regardless of input |
✅ Advantage: Guaranteed O(n log n) in every case — no worst-case degradation like Quick Sort. Also stable (equal elements keep their relative order).
❌ Disadvantage: Needs O(n) EXTRA space for the temporary arrays during merging — not in-place like Quick Sort.
💡 Exam Tip: "Sort the list using MERGESORT and write all steps" questions want BOTH the divide phase (splitting) AND the conquer phase (merging) shown clearly — don't skip straight to the final answer.