{"title":"Merge Sort","description":"","content":"Merge sort is a classic divide-and-conquer algorithm. It repeatedly splits the array into halves until each part contains a single element, then merges those parts back together in sorted order.\n\nIts time complexity is a consistent O(n log n) regardless of the input. Merge sort is also stable and widely used in practice, particularly for linked lists and large datasets that do not fit entirely in memory.\n\n\n\n\n\nThis chapter covers how merge sort works, how to implement it, and why it remains a foundational sorting algorithm.\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. The merge step then combines two sorted subarrays 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, 3]\"]:::secondary\n C[\"[9, 82, 10]\"]:::secondary\n\n D[\"[38, 27]\"]:::secondary\n E[\"[43, 3]\"]:::secondary\n\n F[\"[9, 82]\"]:::secondary\n G[\"[10]\"]:::teal\n\n H[\"[38]\"]:::teal\n I[\"[27]\"]:::teal\n\n J[\"[43]\"]:::teal\n K[\"[3]\"]:::teal\n\n L[\"[9]\"]:::teal\n M[\"[82]\"]:::teal\n\n N[\"[27, 38]\"]:::green\n O[\"[3, 43]\"]:::green\n P[\"[9, 82]\"]:::green\n\n Q[\"[3, 27, 38, 43]\"]:::green\n R[\"[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 D --> H\n D --> I\n E --> J\n E --> K\n F --> L\n F --> M\n\n H -.->|merge| N\n I -.->|merge| N\n J -.->|merge| O\n K -.->|merge| O\n\n L -.->|merge| P\n M -.->|merge| P\n\n N -.->|merge| Q\n O -.->|merge| Q\n P -.->|merge| R\n G -.->|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\nUnlike quicksort, which can degrade to O(n^2) on bad inputs, merge sort always splits the array in half (within one element for odd sizes). That means:\n\n- The recursion tree always has about **log n levels**, since halving the array repeatedly takes log₂ n steps to reach single elements.\n- At each level, every element participates in exactly one merge operation, so the total work across one level is O(n).\n- Multiplying these together gives O(n) work per level times log n levels, or O(n log n) total.\n\nThe input order does not change this. Merge sort does the same amount of work on sorted, reversed, or random input because the splitting and merging structure is fixed.\n\n---\n\n# How It Works\n\nThe algorithm has two core pieces: the recursive splitting logic and the merge procedure.\n\n### The Recursive Structure\n\nThe high-level logic has five steps:\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\nBy the time `merge()` is called, both halves are already sorted: `arr[left..mid]` on the left, `arr[mid+1..right]` on the right. The merge step's only job is to combine them into one sorted range.\n\n### The Merge Procedure\n\nMerging two sorted arrays 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, the algorithm compares the front elements of both halves and picks the smaller one. Because both halves are sorted, 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```go\npackage main\n\n// MergeSort sorts arr in ascending order using merge sort.\nfunc MergeSort(arr []int, left int, right int) {\n\tif left >= right {\n\t\treturn\n\t}\n\n\tmid := left + (right-left)/2\n\tMergeSort(arr, left, mid)\n\tMergeSort(arr, mid+1, right)\n\tmerge(arr, left, mid, right)\n}\n\nfunc merge(arr []int, left int, mid int, right int) {\n\tn1 := mid - left + 1\n\tn2 := right - mid\n\n\tleftArr := make([]int, n1)\n\trightArr := make([]int, n2)\n\n\tfor i := 0; i < n1; i++ {\n\t\tleftArr[i] = arr[left+i]\n\t}\n\tfor j := 0; j < n2; j++ {\n\t\trightArr[j] = arr[mid+1+j]\n\t}\n\n\ti, j, k := 0, 0, left\n\n\tfor i < n1 && j < n2 {\n\t\tif leftArr[i] <= rightArr[j] {\n\t\t\tarr[k] = leftArr[i]\n\t\t\ti++\n\t\t} else {\n\t\t\tarr[k] = rightArr[j]\n\t\t\tj++\n\t\t}\n\t\tk++\n\t}\n\n\tfor i < n1 {\n\t\tarr[k] = leftArr[i]\n\t\ti++\n\t\tk++\n\t}\n\n\tfor j < n2 {\n\t\tarr[k] = rightArr[j]\n\t\tj++\n\t\tk++\n\t}\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```rust\npub struct Solution;\n\nimpl Solution {\n pub fn merge_sort(arr: &mut Vec, left: i32, right: i32) {\n if left >= right {\n return;\n }\n\n let mid = left + (right - left) / 2;\n Self::merge_sort(arr, left, mid);\n Self::merge_sort(arr, mid + 1, right);\n Self::merge(arr, left, mid, right);\n }\n\n fn merge(arr: &mut Vec, left: i32, mid: i32, right: i32) {\n let n1 = mid - left + 1;\n let n2 = right - mid;\n\n let mut left_arr = vec![0; n1 as usize];\n let mut right_arr = vec![0; n2 as usize];\n\n for i in 0..n1 {\n left_arr[i as usize] = arr[(left + i) as usize];\n }\n for j in 0..n2 {\n right_arr[j as usize] = arr[(mid + 1 + j) as usize];\n }\n\n let mut i = 0;\n let mut j = 0;\n let mut k = left as usize;\n\n while i < n1 as usize && j < n2 as usize {\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 }\n k += 1;\n }\n\n while i < n1 as usize {\n arr[k] = left_arr[i];\n i += 1;\n k += 1;\n }\n\n while j < n2 as usize {\n arr[k] = right_arr[j];\n j += 1;\n k += 1;\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\nThe implementation uses `<=` (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, which preserves their original relative order.\n\n\n\n\n\n---\n\n# Example Walkthrough\n\nTrace merge sort on the array `[38, 27, 43, 3, 9, 82, 10]`, following the recursion through both splits and merges. The code uses `mid = left + (right - left) / 2` with `right` inclusive, so a range of size 7 splits into 4 + 3 elements.\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: [38] [27] [43] [3] [9] [82]\n```\n\n\nAt Level 3, every subarray is a single element. Single elements are sorted by definition, so the recursion starts unwinding. The `[10]` subarray at Level 2 is already a single element and waits at this level until its sibling `[9, 82]` finishes.\n\n### Phase 2: Merge (Bottom-Up)\n\nMerging proceeds upward, combining sorted subarrays at each level.\n\n**Merge [38] and [27]:**\n\n\n```shell\nLeft: [38] Right: [27]\ni=0, j=0: Compare 38 vs 27 -> take 27\ni=0 still active, copy remaining from left: 38\nResult: [27, 38]\n```\n\n\n**Merge [43] and [3]:**\n\n\n```shell\nLeft: [43] Right: [3]\ni=0, j=0: Compare 43 vs 3 -> take 3\ni=0 still active, copy remaining from left: 43\nResult: [3, 43]\n```\n\n\n**Merge [27, 38] and [3, 43]:**\n\n\n```shell\nLeft: [27, 38] Right: [3, 43]\ni=0, j=0: Compare 27 vs 3 -> take 3\ni=0, j=1: Compare 27 vs 43 -> take 27\ni=1, j=1: Compare 38 vs 43 -> take 38\ni=2 (exhausted), copy remaining from right: 43\nResult: [3, 27, 38, 43]\n```\n\n\n**Merge [9] and [82]:**\n\n\n```shell\nLeft: [9] Right: [82]\ni=0, j=0: Compare 9 vs 82 -> take 9\ni=1 (exhausted), copy remaining from right: 82\nResult: [9, 82]\n```\n\n\n**Merge [9, 82] and [10]:**\n\n\n```shell\nLeft: [9, 82] Right: [10]\ni=0, j=0: Compare 9 vs 10 -> take 9\ni=1, j=0: Compare 82 vs 10 -> take 10\nj=1 (exhausted), copy remaining from left: 82\nResult: [9, 10, 82]\n```\n\n\n**Final Merge [3, 27, 38, 43] and [9, 10, 82]:**\n\nBoth halves have multiple elements here, so the pointers alternate between sides several times before either half is exhausted.\n\n\n```shell\nLeft: [3, 27, 38, 43] Right: [9, 10, 82]\n\nStep 1: i=0, j=0: Compare 3 vs 9 -> take 3 Result so far: [3]\nStep 2: i=1, j=0: Compare 27 vs 9 -> take 9 Result so far: [3, 9]\nStep 3: i=1, j=1: Compare 27 vs 10 -> take 10 Result so far: [3, 9, 10]\nStep 4: i=1, j=2: Compare 27 vs 82 -> take 27 Result so far: [3, 9, 10, 27]\nStep 5: i=2, j=2: Compare 38 vs 82 -> take 38 Result so far: [3, 9, 10, 27, 38]\nStep 6: i=3, j=2: Compare 43 vs 82 -> take 43 Result so far: [3, 9, 10, 27, 38, 43]\nStep 7: i=4 (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\nThe merge step never goes back or re-examines 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### Stability\n\nMerge sort is **stable**. The merge step uses `<=` (not `<`) when comparing the front elements of the two halves, so an element from the left half is taken first whenever it equals an element on the right. Since the left half originally appeared earlier in the input, equal elements preserve their original order.\n\nThis makes merge sort a common choice when sorting records by multiple fields: a stable sort on the secondary key followed by a stable sort on the primary key produces a result correctly ordered by primary, with ties broken by secondary.\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 trades extra memory for guaranteed performance and stability. Quick sort is typically faster 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.** Merge sort matters in real-time systems or when processing untrusted input that could be adversarially crafted, because worst-case degradation cannot occur.\n- **Sorting linked lists.** Merge sort fits linked lists well because the merge step can be done in O(1) extra space (by re-linking nodes instead of copying to temporary arrays). Splitting does not need random access either, since the midpoint can be found with the fast-slow pointer technique.\n- **External sorting.** When data is too large to fit in memory, the standard approach is to 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.** Sorting records by one field while preserving a previous sort order on another field needs a stable algorithm, and merge sort provides this naturally.\n- **Parallelism.** The two recursive halves are independent of each other, which makes merge sort easy to parallelize. Each half can run 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. For millions of elements in a memory-tight environment, quick sort or heap sort are 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), which is why optimized implementations switch to insertion sort for small subarrays.\n- **Nearly sorted data.** Algorithms like insertion sort or Timsort exploit existing order for O(n) performance on nearly-sorted input. Merge sort does the same amount of work regardless.\n\n---\n\n# Quiz","pageType":"dsa"}

Merge Sort

Get Premium