{"title":"Merge Sort","description":"","content":"Merge Sort is a classic divide-and-conquer algorithm that breaks a problem into smaller, manageable pieces. It repeatedly splits the array into halves until each part contains a single element, then merges those parts back together in sorted order.\n\nThe key idea lies in the merge step, where two sorted arrays are combined efficiently to produce a fully sorted result. This guarantees a consistent time complexity of O(n log n), regardless of the input.\n\nMerge Sort is stable, predictable, and widely used in practice, especially when working with linked lists or large datasets that do not fit entirely in memory.\n\nIn this chapter, you will learn how Merge Sort works step by step, how to implement it, and why it is one of the most important sorting algorithms to understand.\n\n---\n\n# What Is Merge Sort?\n\nMerge sort is a **divide-and-conquer** algorithm. It breaks a problem into smaller subproblems, solves each one independently, and then combines the results. For sorting, that means three steps:\n\n1. **Divide** the array into two halves.\n2. **Conquer** each half by recursively sorting it.\n3. **Combine** the two sorted halves by merging them into one sorted array.\n\nThe recursion bottoms out when a subarray has zero or one element, since a single element is already sorted. Then the magic happens during the merge step, where two sorted subarrays are combined into one.\n\nHere is what the full split-and-merge process looks like for a small array:\n\n\n```mermaid\ngraph TD\n A[\"[38, 27, 43, 3, 9, 82, 10]\"]:::primary\n\n B[\"[38, 27, 43]\"]:::secondary\n C[\"[3, 9, 82, 10]\"]:::secondary\n\n D[\"[38]\"]:::teal\n E[\"[27, 43]\"]:::secondary\n\n F[\"[3, 9]\"]:::secondary\n G[\"[82, 10]\"]:::secondary\n\n H[\"[27]\"]:::teal\n I[\"[43]\"]:::teal\n\n J[\"[3]\"]:::teal\n K[\"[9]\"]:::teal\n\n L[\"[82]\"]:::teal\n M[\"[10]\"]:::teal\n\n N[\"[27, 43]\"]:::green\n O[\"[3, 9]\"]:::green\n P[\"[10, 82]\"]:::green\n\n Q[\"[27, 38, 43]\"]:::green\n R[\"[3, 9, 10, 82]\"]:::green\n\n S[\"[3, 9, 10, 27, 38, 43, 82]\"]:::green\n\n A --> B\n A --> C\n B --> D\n B --> E\n C --> F\n C --> G\n E --> H\n E --> I\n F --> J\n F --> K\n G --> L\n G --> M\n\n H -.->|merge| N\n I -.->|merge| N\n D -.->|merge| Q\n N -.->|merge| Q\n\n J -.->|merge| O\n K -.->|merge| O\n L -.->|merge| P\n M -.->|merge| P\n\n O -.->|merge| R\n P -.->|merge| R\n\n Q -.->|merge| S\n R -.->|merge| S\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe top half of the diagram shows the **divide** phase, where we keep splitting until every subarray has one element. The bottom half shows the **combine** phase, where sorted subarrays merge back together, growing larger at each level until the full array is sorted.\n\n### Why O(n log n) in All Cases?\n\nThis is what makes merge sort special. Unlike quicksort, which can degrade to O(n^2) on bad inputs, merge sort always splits the array exactly in half. That means:\n\n- The recursion tree always has exactly **log n levels** (since we halve the array each time).\n- At each level, every element participates in exactly one merge operation, so the total work per level is **O(n)**.\n- Multiplying these together: **O(n) work per level x log n levels = O(n log n)** total.\n\nThere is no best case or worst case. The input order does not matter. Merge sort always does the same amount of work because the splitting and merging structure is fixed.\n\n---\n\n# How It Works\n\nLet us break down the algorithm into its two core pieces: the recursive splitting logic and the merge procedure.\n\n### The Recursive Structure\n\nThe high-level logic is straightforward:\n\n1. If the array has 0 or 1 elements, return (base case).\n2. Find the midpoint: `mid = left + (right - left) / 2`.\n3. Recursively sort the left half: `mergeSort(arr, left, mid)`.\n4. Recursively sort the right half: `mergeSort(arr, mid + 1, right)`.\n5. Merge the two sorted halves back into the original array.\n\n\n```mermaid\nflowchart TD\n A[\"mergeSort(arr, left, right)\"]:::primary\n B{\"left < right?\"}:::secondary\n C[\"Calculate mid =
left + (right - left) / 2\"]:::teal\n D[\"mergeSort(arr, left, mid)\"]:::primary\n E[\"mergeSort(arr, mid+1, right)\"]:::primary\n F[\"merge(arr, left, mid, right)\"]:::green\n G[\"Return
(base case)\"]:::red\n\n A --> B\n B -->|Yes| C\n B -->|No| G\n C --> D\n D --> E\n E --> F\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\nThe key insight is that by the time we call `merge()`, both halves are already sorted. The left half `arr[left..mid]` is sorted, and the right half `arr[mid+1..right]` is sorted. Our only job is to combine them.\n\n### The Merge Procedure\n\nMerging two sorted arrays is where the real work happens. The idea uses a two-pointer technique:\n\n1. Create a temporary array to hold the merged result.\n2. Place one pointer at the start of the left half and another at the start of the right half.\n3. Compare the elements at both pointers. Copy the smaller one into the temporary array and advance that pointer.\n4. Repeat until one half is exhausted.\n5. Copy any remaining elements from the non-exhausted half.\n6. Copy the temporary array back into the original array.\n\nThis merge step is what gives merge sort its name, and it runs in O(n) time because each element is visited exactly once.\n\n\n```mermaid\nflowchart LR\n subgraph LEFT[\"Left Half (sorted)\"]\n L1[\"3\"]:::teal\n L2[\"27\"]:::teal\n L3[\"38\"]:::teal\n end\n\n subgraph RIGHT[\"Right Half (sorted)\"]\n R1[\"9\"]:::secondary\n R2[\"10\"]:::secondary\n R3[\"43\"]:::secondary\n R4[\"82\"]:::secondary\n end\n\n subgraph MERGED[\"Merged Result\"]\n M1[\"3\"]:::green\n M2[\"9\"]:::green\n M3[\"10\"]:::green\n M4[\"27\"]:::green\n M5[\"38\"]:::green\n M6[\"43\"]:::green\n M7[\"82\"]:::green\n end\n\n LEFT --> MERGED\n RIGHT --> MERGED\n\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef secondary fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nAt each step of the merge, we compare the front elements of both halves and pick the smaller one. Because both halves are sorted, this guarantees the merged result is also sorted.\n\n---\n\n# Code Implementation\n\n\n```java\npublic class MergeSort {\n\n public static void mergeSort(int[] arr, int left, int right) {\n if (left >= right) {\n return;\n }\n\n int mid = left + (right - left) / 2;\n mergeSort(arr, left, mid);\n mergeSort(arr, mid + 1, right);\n merge(arr, left, mid, right);\n }\n\n private static void merge(int[] arr, int left, int mid, int right) {\n int n1 = mid - left + 1;\n int n2 = right - mid;\n\n int[] leftArr = new int[n1];\n int[] rightArr = new int[n2];\n\n for (int i = 0; i < n1; i++) {\n leftArr[i] = arr[left + i];\n }\n for (int j = 0; j < n2; j++) {\n rightArr[j] = arr[mid + 1 + j];\n }\n\n int i = 0, j = 0, k = left;\n\n while (i < n1 && j < n2) {\n if (leftArr[i] <= rightArr[j]) {\n arr[k] = leftArr[i];\n i++;\n } else {\n arr[k] = rightArr[j];\n j++;\n }\n k++;\n }\n\n while (i < n1) {\n arr[k] = leftArr[i];\n i++;\n k++;\n }\n\n while (j < n2) {\n arr[k] = rightArr[j];\n j++;\n k++;\n }\n }\n\n public static void main(String[] args) {\n int[] arr = {38, 27, 43, 3, 9, 82, 10};\n mergeSort(arr, 0, arr.length - 1);\n // arr is now [3, 9, 10, 27, 38, 43, 82]\n }\n}\n```\n\n```python\ndef merge_sort(arr, left, right):\n if left >= right:\n return\n\n mid = left + (right - left) // 2\n merge_sort(arr, left, mid)\n merge_sort(arr, mid + 1, right)\n merge(arr, left, mid, right)\n\ndef merge(arr, left, mid, right):\n left_arr = arr[left:mid + 1]\n right_arr = arr[mid + 1:right + 1]\n\n i = 0\n j = 0\n k = left\n\n while i < len(left_arr) and j < len(right_arr):\n if left_arr[i] <= right_arr[j]:\n arr[k] = left_arr[i]\n i += 1\n else:\n arr[k] = right_arr[j]\n j += 1\n k += 1\n\n while i < len(left_arr):\n arr[k] = left_arr[i]\n i += 1\n k += 1\n\n while j < len(right_arr):\n arr[k] = right_arr[j]\n j += 1\n k += 1\n\nif __name__ == \"__main__\":\n arr = [38, 27, 43, 3, 9, 82, 10]\n merge_sort(arr, 0, len(arr) - 1)\n # arr is now [3, 9, 10, 27, 38, 43, 82]\n```\n\n```cpp\n#include \n\nvoid merge(std::vector& arr, int left, int mid, int right) {\n int n1 = mid - left + 1;\n int n2 = right - mid;\n\n std::vector leftArr(n1);\n std::vector rightArr(n2);\n\n for (int i = 0; i < n1; i++) {\n leftArr[i] = arr[left + i];\n }\n for (int j = 0; j < n2; j++) {\n rightArr[j] = arr[mid + 1 + j];\n }\n\n int i = 0, j = 0, k = left;\n\n while (i < n1 && j < n2) {\n if (leftArr[i] <= rightArr[j]) {\n arr[k] = leftArr[i];\n i++;\n } else {\n arr[k] = rightArr[j];\n j++;\n }\n k++;\n }\n\n while (i < n1) {\n arr[k] = leftArr[i];\n i++;\n k++;\n }\n\n while (j < n2) {\n arr[k] = rightArr[j];\n j++;\n k++;\n }\n}\n\nvoid mergeSort(std::vector& arr, int left, int right) {\n if (left >= right) {\n return;\n }\n\n int mid = left + (right - left) / 2;\n mergeSort(arr, left, mid);\n mergeSort(arr, mid + 1, right);\n merge(arr, left, mid, right);\n}\n```\n\n```csharp\npublic class MergeSort\n{\n public static void Sort(int[] arr, int left, int right)\n {\n if (left >= right)\n {\n return;\n }\n\n int mid = left + (right - left) / 2;\n Sort(arr, left, mid);\n Sort(arr, mid + 1, right);\n Merge(arr, left, mid, right);\n }\n\n private static void Merge(int[] arr, int left, int mid, int right)\n {\n int n1 = mid - left + 1;\n int n2 = right - mid;\n\n int[] leftArr = new int[n1];\n int[] rightArr = new int[n2];\n\n for (int i = 0; i < n1; i++)\n {\n leftArr[i] = arr[left + i];\n }\n for (int j = 0; j < n2; j++)\n {\n rightArr[j] = arr[mid + 1 + j];\n }\n\n int li = 0, ri = 0, k = left;\n\n while (li < n1 && ri < n2)\n {\n if (leftArr[li] <= rightArr[ri])\n {\n arr[k] = leftArr[li];\n li++;\n }\n else\n {\n arr[k] = rightArr[ri];\n ri++;\n }\n k++;\n }\n\n while (li < n1)\n {\n arr[k] = leftArr[li];\n li++;\n k++;\n }\n\n while (ri < n2)\n {\n arr[k] = rightArr[ri];\n ri++;\n k++;\n }\n }\n}\n```\n\n```javascript\nfunction mergeSort(arr, left, right) {\n if (left >= right) {\n return;\n }\n\n const mid = left + Math.floor((right - left) / 2);\n mergeSort(arr, left, mid);\n mergeSort(arr, mid + 1, right);\n merge(arr, left, mid, right);\n}\n\nfunction merge(arr, left, mid, right) {\n const leftArr = arr.slice(left, mid + 1);\n const rightArr = arr.slice(mid + 1, right + 1);\n\n let i = 0;\n let j = 0;\n let k = left;\n\n while (i < leftArr.length && j < rightArr.length) {\n if (leftArr[i] <= rightArr[j]) {\n arr[k] = leftArr[i];\n i++;\n } else {\n arr[k] = rightArr[j];\n j++;\n }\n k++;\n }\n\n while (i < leftArr.length) {\n arr[k] = leftArr[i];\n i++;\n k++;\n }\n\n while (j < rightArr.length) {\n arr[k] = rightArr[j];\n j++;\n k++;\n }\n}\n\n// Usage\nconst arr = [38, 27, 43, 3, 9, 82, 10];\nmergeSort(arr, 0, arr.length - 1);\n// arr is now [3, 9, 10, 27, 38, 43, 82]\n```\n\n```typescript\nfunction mergeSort(arr: number[], left: number, right: number): void {\n if (left >= right) {\n return;\n }\n\n const mid = left + Math.floor((right - left) / 2);\n mergeSort(arr, left, mid);\n mergeSort(arr, mid + 1, right);\n merge(arr, left, mid, right);\n}\n\nfunction merge(arr: number[], left: number, mid: number, right: number): void {\n const leftArr: number[] = arr.slice(left, mid + 1);\n const rightArr: number[] = arr.slice(mid + 1, right + 1);\n\n let i = 0;\n let j = 0;\n let k = left;\n\n while (i < leftArr.length && j < rightArr.length) {\n if (leftArr[i] <= rightArr[j]) {\n arr[k] = leftArr[i];\n i++;\n } else {\n arr[k] = rightArr[j];\n j++;\n }\n k++;\n }\n\n while (i < leftArr.length) {\n arr[k] = leftArr[i];\n i++;\n k++;\n }\n\n while (j < rightArr.length) {\n arr[k] = rightArr[j];\n j++;\n k++;\n }\n}\n\n// Usage\nconst arr: number[] = [38, 27, 43, 3, 9, 82, 10];\nmergeSort(arr, 0, arr.length - 1);\n// arr is now [3, 9, 10, 27, 38, 43, 82]\n```\n\n\nNotice that the implementations use `<=` (not `<`) when comparing elements from the left and right halves. This is what makes merge sort **stable**: equal elements from the left half always come before equal elements from the right half, preserving their original relative order.\n\n\n\n\n---\n\n# Example Walkthrough\n\nLet us trace through merge sort step by step with the array `[38, 27, 43, 3, 9, 82, 10]`. Following the recursion carefully helps you understand exactly when splits and merges happen.\n\n### Phase 1: Divide\n\nThe algorithm splits the array recursively until every subarray has at most one element.\n\n\n```shell\nLevel 0: [38, 27, 43, 3, 9, 82, 10]\n / \\\nLevel 1: [38, 27, 43] [3, 9, 82, 10]\n / \\ / \\\nLevel 2: [38] [27, 43] [3, 9] [82, 10]\n / \\ / \\ / \\\nLevel 3: [27] [43] [3] [9] [82] [10]\n```\n\n\nAt Level 3, every subarray is a single element. Single elements are sorted by definition, so the recursion starts unwinding.\n\n### Phase 2: Merge (Bottom-Up)\n\nNow we merge back up, combining sorted subarrays at each level.\n\n**Merge [27] and [43]:**\n\n\n```shell\nLeft: [27] Right: [43]\ni=0, j=0: Compare 27 vs 43 -> take 27\ni=1 (exhausted), copy remaining from right: 43\nResult: [27, 43]\n```\n\n\n**Merge [38] and [27, 43]:**\n\n\n```shell\nLeft: [38] Right: [27, 43]\ni=0, j=0: Compare 38 vs 27 -> take 27\ni=0, j=1: Compare 38 vs 43 -> take 38\ni=1 (exhausted), copy remaining from right: 43\nResult: [27, 38, 43]\n```\n\n\n**Merge [3] and [9]:**\n\n\n```shell\nLeft: [3] Right: [9]\ni=0, j=0: Compare 3 vs 9 -> take 3\ni=1 (exhausted), copy remaining from right: 9\nResult: [3, 9]\n```\n\n\n**Merge [82] and [10]:**\n\n\n```shell\nLeft: [82] Right: [10]\ni=0, j=0: Compare 82 vs 10 -> take 10\nj=1 (exhausted), copy remaining from left: 82\nResult: [10, 82]\n```\n\n\n**Merge [3, 9] and [10, 82]:**\n\n\n```shell\nLeft: [3, 9] Right: [10, 82]\ni=0, j=0: Compare 3 vs 10 -> take 3\ni=1, j=0: Compare 9 vs 10 -> take 9\ni=2 (exhausted), copy remaining from right: 10, 82\nResult: [3, 9, 10, 82]\n```\n\n\n**Final Merge [27, 38, 43] and [3, 9, 10, 82]:**\n\nThis is the most interesting merge because both halves have multiple elements and the pointers alternate between sides.\n\n\n```shell\nLeft: [27, 38, 43] Right: [3, 9, 10, 82]\n\nStep 1: i=0, j=0: Compare 27 vs 3 -> take 3 Result so far: [3]\nStep 2: i=0, j=1: Compare 27 vs 9 -> take 9 Result so far: [3, 9]\nStep 3: i=0, j=2: Compare 27 vs 10 -> take 10 Result so far: [3, 9, 10]\nStep 4: i=0, j=3: Compare 27 vs 82 -> take 27 Result so far: [3, 9, 10, 27]\nStep 5: i=1, j=3: Compare 38 vs 82 -> take 38 Result so far: [3, 9, 10, 27, 38]\nStep 6: i=2, j=3: Compare 43 vs 82 -> take 43 Result so far: [3, 9, 10, 27, 38, 43]\nStep 7: i=3 (exhausted), copy remaining: 82 Result: [3, 9, 10, 27, 38, 43, 82]\n```\n\n\nThe final sorted array is `[3, 9, 10, 27, 38, 43, 82]`.\n\nNotice how the merge step never needs to \"go back\" or re-examine elements. Each element is compared and placed exactly once per merge, which is why each merge level takes O(n) total work.\n\n---\n\n# Complexity Analysis\n\n\n| Case | Time Complexity | Explanation |\n|------|----------------|-------------|\n| Best | O(n log n) | Always splits in half, always merges. No shortcuts. |\n| Average | O(n log n) | Same structure regardless of input order. |\n| Worst | O(n log n) | Same. The split-merge structure is input-independent. |\n| Space | O(n) | Temporary arrays used during merge. |\n| Stable | Yes | Equal elements maintain their relative order. |\n\n\n### Why O(n) Space?\n\nEach merge step creates temporary arrays to hold the two halves being merged. At the top level, the temporary arrays hold all n elements. While deeper recursion levels use smaller arrays, those arrays are freed before the top-level merge begins (since recursion unwinds bottom-up). So the peak additional memory usage is O(n).\n\nThe call stack also uses O(log n) space due to the recursion depth, but this is dominated by the O(n) temporary arrays.\n\n### Comparison with Other O(n log n) Sorts\n\n\n| Property | Merge Sort | Quick Sort | Heap Sort |\n|----------|-----------|------------|-----------|\n| Worst-case time | O(n log n) | O(n^2) | O(n log n) |\n| Average time | O(n log n) | O(n log n) | O(n log n) |\n| Space | O(n) | O(log n) | O(1) |\n| Stable | Yes | No | No |\n| Cache-friendly | Moderate | Excellent | Poor |\n| In-place | No | Yes | Yes |\n\n\nMerge sort's trade-off is clear: guaranteed performance and stability at the cost of extra memory. Quick sort is typically faster in practice due to better cache locality, but it cannot guarantee O(n log n) without careful pivot selection.\n\n---\n\n# When to Use Merge Sort\n\n### Good For\n\n- **Guaranteed O(n log n) performance.** When you cannot afford worst-case degradation, merge sort is the safe choice. This matters in real-time systems or when processing untrusted input that could be adversarially crafted.\n- **Sorting linked lists.** Merge sort is ideal for linked lists because the merge step can be done in O(1) extra space (by re-linking nodes instead of copying to temporary arrays). You also do not need random access for splitting, since you can find the midpoint with the fast-slow pointer technique.\n- **External sorting.** When data is too large to fit in memory, you split it into chunks that fit in RAM, sort each chunk with any algorithm, and then merge the sorted chunks. This multi-way merge is the foundation of how databases and big data systems sort terabytes of data.\n- **Stability is required.** If you need equal elements to keep their original relative order (for example, sorting records by one field while preserving a previous sort order on another field), merge sort naturally provides this.\n- **Parallelism.** The two recursive halves are independent of each other, making merge sort easy to parallelize. You can sort each half on a different thread or even a different machine.\n\n### Not Ideal For\n\n- **Memory-constrained environments.** The O(n) extra space is a real cost. If you are sorting millions of elements in a memory-tight environment, quick sort or heap sort might be better choices.\n- **Small arrays.** The overhead of recursion and temporary array creation makes merge sort slower than simpler algorithms like insertion sort for small arrays (typically n < 20-30). This is why optimized implementations switch to insertion sort for small subarrays.\n- **Nearly sorted data.** Algorithms like insertion sort or Timsort can exploit existing order for O(n) performance on nearly-sorted input. Merge sort does the same amount of work regardless.","pageType":"dsa"}

Merge Sort

Ashish Pratap Singh

Get Premium