{"title":"Divide and Conquer","description":"","content":"Imagine you have a massive pile of unsorted exam papers and you need to arrange them alphabetically. Sorting the entire pile at once feels overwhelming. But what if you split the pile in half, sort each half separately, and then merge the two sorted halves together? Suddenly, the task feels manageable. And here is the clever part: you can keep splitting each half into smaller halves, all the way down until you are dealing with single papers that are trivially \"sorted.\"\n\nThis is divide and conquer in a nutshell. It is one of the most elegant algorithmic strategies ever invented, and it powers some of the most important algorithms in computer science, from merge sort to binary search to the fast Fourier transform. Once you understand the framework, you will start recognizing it everywhere.\n\nIn this chapter, we will break down the divide and conquer pattern, understand why splitting problems actually reduces work, learn the Master Theorem for analyzing these algorithms, and walk through classic examples step by step.\n\n---\n\n# What Is Divide and Conquer?\n\nDivide and conquer is a problem-solving strategy that works in three steps:\n\n1. **Divide**: Break the problem into smaller subproblems of the same type.\n2. **Conquer**: Solve each subproblem recursively. When a subproblem is small enough, solve it directly (the base case).\n3. **Combine**: Merge the solutions of the subproblems to produce the solution to the original problem.\n\nThe key idea is that working on smaller pieces is easier, and if you can combine the small results efficiently, the overall algorithm becomes faster than tackling the whole problem head-on.\n\nHere is how the general pattern looks:\n\n\n```mermaid\nflowchart TD\n A[\"Original Problem
(size n)\"]\n\n A --> B[\"Subproblem 1
(size n/2)\"]\n A --> C[\"Subproblem 2
(size n/2)\"]\n\n B --> D[\"Sub-sub 1
(size n/4)\"]\n B --> E[\"Sub-sub 2
(size n/4)\"]\n\n C --> F[\"Sub-sub 3
(size n/4)\"]\n C --> G[\"Sub-sub 4
(size n/4)\"]\n\n D --> H[\"Base Case\"]\n E --> I[\"Base Case\"]\n F --> J[\"Base Case\"]\n G --> K[\"Base Case\"]\n\n H --> L[\"Combine\"]\n I --> L\n L --> N[\"Combine\"]\n\n J --> M[\"Combine\"]\n K --> M\n M --> N\n\n N --> O[\"Final Solution\"]\n\n style A fill:#00ceff,stroke:#000,color:#000\n style B fill:#ffa94d,stroke:#000,color:#000\n style C fill:#ffa94d,stroke:#000,color:#000\n style D fill:#38d9a9,stroke:#000,color:#000\n style E fill:#38d9a9,stroke:#000,color:#000\n style F fill:#38d9a9,stroke:#000,color:#000\n style G fill:#38d9a9,stroke:#000,color:#000\n style H fill:#69db7c,stroke:#000,color:#000\n style I fill:#69db7c,stroke:#000,color:#000\n style J fill:#69db7c,stroke:#000,color:#000\n style K fill:#69db7c,stroke:#000,color:#000\n style L fill:#ffa94d,stroke:#000,color:#000\n style M fill:#ffa94d,stroke:#000,color:#000\n style N fill:#00ceff,stroke:#000,color:#000\n style O fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe diagram shows the two phases of divide and conquer. The top half is the **divide** phase, where we recursively split the problem until we reach base cases. The bottom half is the **combine** phase, where we merge results back up to form the final solution.\n\nLet us look at a simple example. Say you want to find the maximum element in an array `[3, 7, 2, 9, 1, 5]`. A straightforward approach scans every element. With divide and conquer, you split the array into two halves, find the max of each half recursively, and then return the larger of the two results. Both approaches take O(n) time for this particular problem, but this simple example illustrates the structure that, for other problems, leads to dramatic speedups.\n\n---\n\n# Why Does Splitting Work?\n\nThis is the natural question. If we still have to look at every element eventually, why is dividing the problem helpful?\n\nThe answer depends on the **combine step**. When the combine step is efficient, and when splitting reduces the total number of operations across all levels, divide and conquer wins big.\n\nConsider sorting. A brute-force approach like selection sort works by scanning the entire array to find the minimum, placing it first, then scanning the remaining elements for the next minimum, and so on. Each scan takes O(n) time, and you need n scans. That gives O(n^2).\n\nNow think about merge sort. You split the array into two halves and sort each half. Sorting each half takes roughly half the work (since they are half the size). Then you merge the two sorted halves, which takes O(n) time because you just walk through both halves simultaneously. The total work at each level of recursion is O(n), and there are log(n) levels, so the total is O(n log n). That is a huge improvement over O(n^2).\n\nHere is the intuition: each level of recursion does O(n) total work, but there are only log(n) levels instead of n levels.\n\n\n| Approach | Work per Level | Number of Levels | Total |\n|----------|---------------|-----------------|-------|\n| Selection Sort (brute force) | O(n) | n | O(n^2) |\n| Merge Sort (divide and conquer) | O(n) | log n | O(n log n) |\n\n\nFor an array of 1 million elements, that is the difference between 10^12 operations and roughly 20 million operations. Divide and conquer does not just help a little. It transforms what is feasible.\n\nThe magic happens when two conditions are met:\n\n1. **Subproblems are independent.** Solving one does not depend on the result of another.\n2. **The combine step is efficient.** Merging results does not take more work than solving the original problem would.\n\nWhen both conditions hold, divide and conquer turns problems that seem inherently quadratic (or worse) into something much more efficient.\n\n---\n\n# The Divide and Conquer Template\n\nEvery divide and conquer algorithm follows the same skeleton. Here is a generic Java template:\n\n\n```java\npublic Result solve(Problem problem) {\n // Base case: problem is small enough to solve directly\n if (isBaseCase(problem)) {\n return solveDirectly(problem);\n }\n\n // DIVIDE: Split into subproblems\n Problem left = getLeftHalf(problem);\n Problem right = getRightHalf(problem);\n\n // CONQUER: Solve subproblems recursively\n Result leftResult = solve(left);\n Result rightResult = solve(right);\n\n // COMBINE: Merge the results\n return combine(leftResult, rightResult);\n}\n```\n\n```python\ndef solve(problem):\n # Base case: problem is small enough to solve directly\n if isBaseCase(problem):\n return solveDirectly(problem)\n\n # DIVIDE: Split into subproblems\n left = getLeftHalf(problem)\n right = getRightHalf(problem)\n\n # CONQUER: Solve subproblems recursively\n leftResult = solve(left)\n rightResult = solve(right)\n\n # COMBINE: Merge the results\n return combine(leftResult, rightResult)\n```\n\n```cpp\nResult solve(Problem problem) {\n // Base case: problem is small enough to solve directly\n if (isBaseCase(problem)) {\n return solveDirectly(problem);\n }\n\n // DIVIDE: Split into subproblems\n Problem left = getLeftHalf(problem);\n Problem right = getRightHalf(problem);\n\n // CONQUER: Solve subproblems recursively\n Result leftResult = solve(left);\n Result rightResult = solve(right);\n\n // COMBINE: Merge the results\n return combine(leftResult, rightResult);\n}\n```\n\n```go\nfunc solve(problem Problem) Result {\n\t// Base case: problem is small enough to solve directly\n\tif isBaseCase(problem) {\n\t\treturn solveDirectly(problem)\n\t}\n\n\t// DIVIDE: Split into subproblems\n\tleft := getLeftHalf(problem)\n\tright := getRightHalf(problem)\n\n\t// CONQUER: Solve subproblems recursively\n\tleftResult := solve(left)\n\trightResult := solve(right)\n\n\t// COMBINE: Merge the results\n\treturn combine(leftResult, rightResult)\n}\n```\n\n```csharp\npublic Result solve(Problem problem)\n{\n // Base case: problem is small enough to solve directly\n if (isBaseCase(problem))\n {\n return solveDirectly(problem);\n }\n\n // DIVIDE: Split into subproblems\n Problem left = getLeftHalf(problem);\n Problem right = getRightHalf(problem);\n\n // CONQUER: Solve subproblems recursively\n Result leftResult = solve(left);\n Result rightResult = solve(right);\n\n // COMBINE: Merge the results\n return combine(leftResult, rightResult);\n}\n```\n\n```rust\nfn solve(problem: Problem) -> Result {\n // Base case: problem is small enough to solve directly\n if isBaseCase(problem) {\n return solveDirectly(problem);\n }\n\n // DIVIDE: Split into subproblems\n let left = getLeftHalf(problem);\n let right = getRightHalf(problem);\n\n // CONQUER: Solve subproblems recursively\n let leftResult = solve(left);\n let rightResult = solve(right);\n\n // COMBINE: Merge the results\n combine(leftResult, rightResult)\n}\n```\n\n```javascript\nfunction solve(problem) {\n // Base case: problem is small enough to solve directly\n if (isBaseCase(problem)) {\n return solveDirectly(problem);\n }\n\n // DIVIDE: Split into subproblems\n const left = getLeftHalf(problem);\n const right = getRightHalf(problem);\n\n // CONQUER: Solve subproblems recursively\n const leftResult = solve(left);\n const rightResult = solve(right);\n\n // COMBINE: Merge the results\n return combine(leftResult, rightResult);\n}\n```\n\n```typescript\npublic solve(problem: Problem): Result {\n // Base case: problem is small enough to solve directly\n if (isBaseCase(problem)) {\n return solveDirectly(problem);\n }\n\n // DIVIDE: Split into subproblems\n const left = getLeftHalf(problem);\n const right = getRightHalf(problem);\n\n // CONQUER: Solve subproblems recursively\n const leftResult = this.solve(left);\n const rightResult = this.solve(right);\n\n // COMBINE: Merge the results\n return combine(leftResult, rightResult);\n}\n```\n\n\nLet us break down each component:\n\n#### **Base case**\n\nThis is where recursion stops. For most divide and conquer problems, the base case is when the input has zero or one element. Getting this right is critical. If your base case is wrong, the recursion either never terminates or produces incorrect results.\n\n#### **Divide**\n\nThis step splits the problem into two (or more) subproblems. The split should be roughly equal to get the best performance. An unbalanced split (like 1 element and n-1 elements) can degrade performance from O(n log n) to O(n^2), as we will see with quick sort's worst case.\n\n#### **Conquer**\n\nSolve each subproblem by calling the same function recursively. The recursion naturally handles the repeated splitting until base cases are reached.\n\n#### **Combine**\n\nThis is often where the real cleverness lies. The combine step determines the overall efficiency of the algorithm. A cheap combine step (O(1) or O(n)) leads to efficient algorithms. An expensive combine step can negate the benefits of splitting.\n\n---\n\n# Example Walkthrough: Merge Sort\n\nMerge sort is the textbook example of divide and conquer. It perfectly illustrates all three steps: split the array in half, recursively sort each half, and merge the sorted halves.\n\n### Java Implementation\n\n\n```java\npublic class MergeSort {\n\n public void mergeSort(int[] arr, int left, int right) {\n // Base case: a single element or empty subarray is already sorted\n if (left >= right) {\n return;\n }\n\n // DIVIDE: Find the midpoint\n int mid = left + (right - left) / 2;\n\n // CONQUER: Sort each half recursively\n mergeSort(arr, left, mid);\n mergeSort(arr, mid + 1, right);\n\n // COMBINE: Merge the two sorted halves\n merge(arr, left, mid, right);\n }\n\n private void merge(int[] arr, int left, int mid, int right) {\n // Create temporary arrays for the two halves\n int[] leftArr = new int[mid - left + 1];\n int[] rightArr = new int[right - mid];\n\n // Copy data into temporary arrays\n for (int i = 0; i < leftArr.length; i++) {\n leftArr[i] = arr[left + i];\n }\n for (int i = 0; i < rightArr.length; i++) {\n rightArr[i] = arr[mid + 1 + i];\n }\n\n // Merge the two sorted halves back into the original array\n int i = 0, j = 0, k = left;\n while (i < leftArr.length && j < rightArr.length) {\n if (leftArr[i] <= rightArr[j]) {\n arr[k++] = leftArr[i++];\n } else {\n arr[k++] = rightArr[j++];\n }\n }\n\n // Copy any remaining elements\n while (i < leftArr.length) {\n arr[k++] = leftArr[i++];\n }\n while (j < rightArr.length) {\n arr[k++] = rightArr[j++];\n }\n }\n}\n```\n\n```python\nclass MergeSort:\n def mergeSort(self, arr, left, right):\n # Base case: a single element or empty subarray is already sorted\n if left >= right:\n return\n\n # DIVIDE: Find the midpoint\n mid = left + (right - left) // 2\n\n # CONQUER: Sort each half recursively\n self.mergeSort(arr, left, mid)\n self.mergeSort(arr, mid + 1, right)\n\n # COMBINE: Merge the two sorted halves\n self.merge(arr, left, mid, right)\n\n def merge(self, arr, left, mid, right):\n # Create temporary arrays for the two halves\n leftArr = [0] * (mid - left + 1)\n rightArr = [0] * (right - mid)\n\n # Copy data into temporary arrays\n for i in range(len(leftArr)):\n leftArr[i] = arr[left + i]\n for i in range(len(rightArr)):\n rightArr[i] = arr[mid + 1 + i]\n\n # Merge the two sorted halves back into the original array\n i = 0\n j = 0\n k = left\n while i < len(leftArr) and j < len(rightArr):\n if leftArr[i] <= rightArr[j]:\n arr[k] = leftArr[i]\n i += 1\n else:\n arr[k] = rightArr[j]\n j += 1\n k += 1\n\n # Copy any remaining elements\n while i < len(leftArr):\n arr[k] = leftArr[i]\n i += 1\n k += 1\n while j < len(rightArr):\n arr[k] = rightArr[j]\n j += 1\n k += 1\n```\n\n```cpp\nclass MergeSort {\npublic:\n void mergeSort(std::vector& arr, int left, int right) {\n // Base case: a single element or empty subarray is already sorted\n if (left >= right) {\n return;\n }\n\n // DIVIDE: Find the midpoint\n int mid = left + (right - left) / 2;\n\n // CONQUER: Sort each half recursively\n mergeSort(arr, left, mid);\n mergeSort(arr, mid + 1, right);\n\n // COMBINE: Merge the two sorted halves\n merge(arr, left, mid, right);\n }\n\nprivate:\n void merge(std::vector& arr, int left, int mid, int right) {\n // Create temporary arrays for the two halves\n std::vector leftArr(mid - left + 1);\n std::vector rightArr(right - mid);\n\n // Copy data into temporary arrays\n for (int i = 0; i < (int)leftArr.size(); i++) {\n leftArr[i] = arr[left + i];\n }\n for (int i = 0; i < (int)rightArr.size(); i++) {\n rightArr[i] = arr[mid + 1 + i];\n }\n\n // Merge the two sorted halves back into the original array\n int i = 0, j = 0, k = left;\n while (i < (int)leftArr.size() && j < (int)rightArr.size()) {\n if (leftArr[i] <= rightArr[j]) {\n arr[k++] = leftArr[i++];\n } else {\n arr[k++] = rightArr[j++];\n }\n }\n\n // Copy any remaining elements\n while (i < (int)leftArr.size()) {\n arr[k++] = leftArr[i++];\n }\n while (j < (int)rightArr.size()) {\n arr[k++] = rightArr[j++];\n }\n }\n};\n```\n\n```go\ntype MergeSort struct{}\n\nfunc (m *MergeSort) MergeSort(arr []int, left int, right int) {\n\t// Base case: a single element or empty subarray is already sorted\n\tif left >= right {\n\t\treturn\n\t}\n\n\t// DIVIDE: Find the midpoint\n\tmid := left + (right-left)/2\n\n\t// CONQUER: Sort each half recursively\n\tm.MergeSort(arr, left, mid)\n\tm.MergeSort(arr, mid+1, right)\n\n\t// COMBINE: Merge the two sorted halves\n\tm.merge(arr, left, mid, right)\n}\n\nfunc (m *MergeSort) merge(arr []int, left int, mid int, right int) {\n\t// Create temporary arrays for the two halves\n\tleftArr := make([]int, mid-left+1)\n\trightArr := make([]int, right-mid)\n\n\t// Copy data into temporary arrays\n\tfor i := 0; i < len(leftArr); i++ {\n\t\tleftArr[i] = arr[left+i]\n\t}\n\tfor i := 0; i < len(rightArr); i++ {\n\t\trightArr[i] = arr[mid+1+i]\n\t}\n\n\t// Merge the two sorted halves back into the original array\n\ti, j, k := 0, 0, left\n\tfor i < len(leftArr) && j < len(rightArr) {\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\t// Copy any remaining elements\n\tfor i < len(leftArr) {\n\t\tarr[k] = leftArr[i]\n\t\ti++\n\t\tk++\n\t}\n\tfor j < len(rightArr) {\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 void MergeSort(int[] arr, int left, int right)\n {\n // Base case: a single element or empty subarray is already sorted\n if (left >= right)\n {\n return;\n }\n\n // DIVIDE: Find the midpoint\n int mid = left + (right - left) / 2;\n\n // CONQUER: Sort each half recursively\n MergeSort(arr, left, mid);\n MergeSort(arr, mid + 1, right);\n\n // COMBINE: Merge the two sorted halves\n Merge(arr, left, mid, right);\n }\n\n private void Merge(int[] arr, int left, int mid, int right)\n {\n // Create temporary arrays for the two halves\n int[] leftArr = new int[mid - left + 1];\n int[] rightArr = new int[right - mid];\n\n // Copy data into temporary arrays\n for (int i = 0; i < leftArr.Length; i++)\n {\n leftArr[i] = arr[left + i];\n }\n for (int i = 0; i < rightArr.Length; i++)\n {\n rightArr[i] = arr[mid + 1 + i];\n }\n\n // Merge the two sorted halves back into the original array\n int i = 0, j = 0, k = left;\n while (i < leftArr.Length && j < rightArr.Length)\n {\n if (leftArr[i] <= rightArr[j])\n {\n arr[k++] = leftArr[i++];\n }\n else\n {\n arr[k++] = rightArr[j++];\n }\n }\n\n // Copy any remaining elements\n while (i < leftArr.Length)\n {\n arr[k++] = leftArr[i++];\n }\n while (j < rightArr.Length)\n {\n arr[k++] = rightArr[j++];\n }\n }\n}\n```\n\n```rust\npub struct MergeSort;\n\nimpl MergeSort {\n pub fn merge_sort(&mut self, arr: &mut [i32], left: usize, right: usize) {\n // Base case: a single element or empty subarray is already sorted\n if left >= right {\n return;\n }\n\n // DIVIDE: Find the midpoint\n let mid = left + (right - left) / 2;\n\n // CONQUER: Sort each half recursively\n self.merge_sort(arr, left, mid);\n self.merge_sort(arr, mid + 1, right);\n\n // COMBINE: Merge the two sorted halves\n self.merge(arr, left, mid, right);\n }\n\n fn merge(&self, arr: &mut [i32], left: usize, mid: usize, right: usize) {\n // Create temporary arrays for the two halves\n let mut left_arr = vec![0; mid - left + 1];\n let mut right_arr = vec![0; right - mid];\n\n // Copy data into temporary arrays\n for i in 0..left_arr.len() {\n left_arr[i] = arr[left + i];\n }\n for i in 0..right_arr.len() {\n right_arr[i] = arr[mid + 1 + i];\n }\n\n // Merge the two sorted halves back into the original array\n let mut i = 0;\n let mut j = 0;\n let mut k = left;\n while i < left_arr.len() && j < right_arr.len() {\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 // Copy any remaining elements\n while i < left_arr.len() {\n arr[k] = left_arr[i];\n i += 1;\n k += 1;\n }\n while j < right_arr.len() {\n arr[k] = right_arr[j];\n j += 1;\n k += 1;\n }\n }\n}\n```\n\n```javascript\nclass MergeSort {\n mergeSort(arr, left, right) {\n // Base case: a single element or empty subarray is already sorted\n if (left >= right) {\n return;\n }\n\n // DIVIDE: Find the midpoint\n const mid = left + Math.floor((right - left) / 2);\n\n // CONQUER: Sort each half recursively\n this.mergeSort(arr, left, mid);\n this.mergeSort(arr, mid + 1, right);\n\n // COMBINE: Merge the two sorted halves\n this.merge(arr, left, mid, right);\n }\n\n merge(arr, left, mid, right) {\n // Create temporary arrays for the two halves\n const leftArr = new Array(mid - left + 1);\n const rightArr = new Array(right - mid);\n\n // Copy data into temporary arrays\n for (let i = 0; i < leftArr.length; i++) {\n leftArr[i] = arr[left + i];\n }\n for (let i = 0; i < rightArr.length; i++) {\n rightArr[i] = arr[mid + 1 + i];\n }\n\n // Merge the two sorted halves back into the original array\n let i = 0, j = 0, k = left;\n while (i < leftArr.length && j < rightArr.length) {\n if (leftArr[i] <= rightArr[j]) {\n arr[k++] = leftArr[i++];\n } else {\n arr[k++] = rightArr[j++];\n }\n }\n\n // Copy any remaining elements\n while (i < leftArr.length) {\n arr[k++] = leftArr[i++];\n }\n while (j < rightArr.length) {\n arr[k++] = rightArr[j++];\n }\n }\n}\n```\n\n```typescript\nclass MergeSort {\n mergeSort(arr: number[], left: number, right: number): void {\n // Base case: a single element or empty subarray is already sorted\n if (left >= right) {\n return;\n }\n\n // DIVIDE: Find the midpoint\n const mid = left + Math.floor((right - left) / 2);\n\n // CONQUER: Sort each half recursively\n this.mergeSort(arr, left, mid);\n this.mergeSort(arr, mid + 1, right);\n\n // COMBINE: Merge the two sorted halves\n this.merge(arr, left, mid, right);\n }\n\n private merge(arr: number[], left: number, mid: number, right: number): void {\n // Create temporary arrays for the two halves\n const leftArr: number[] = new Array(mid - left + 1);\n const rightArr: number[] = new Array(right - mid);\n\n // Copy data into temporary arrays\n for (let i = 0; i < leftArr.length; i++) {\n leftArr[i] = arr[left + i];\n }\n for (let i = 0; i < rightArr.length; i++) {\n rightArr[i] = arr[mid + 1 + i];\n }\n\n // Merge the two sorted halves back into the original array\n let i = 0, j = 0, k = left;\n while (i < leftArr.length && j < rightArr.length) {\n if (leftArr[i] <= rightArr[j]) {\n arr[k++] = leftArr[i++];\n } else {\n arr[k++] = rightArr[j++];\n }\n }\n\n // Copy any remaining elements\n while (i < leftArr.length) {\n arr[k++] = leftArr[i++];\n }\n while (j < rightArr.length) {\n arr[k++] = rightArr[j++];\n }\n }\n}\n```\n\n\n### Step-by-Step Trace\n\nLet us trace merge sort on the array `[38, 27, 43, 3, 9, 82, 10]`.\n\n\n```shell\nDIVIDE phase:\n[38, 27, 43, 3, 9, 82, 10]\n├── [38, 27, 43, 3]\n│ ├── [38, 27]\n│ │ ├── [38] (base case)\n│ │ └── [27] (base case)\n│ └── [43, 3]\n│ ├── [43] (base case)\n│ └── [3] (base case)\n└── [9, 82, 10]\n ├── [9, 82]\n │ ├── [9] (base case)\n │ └── [82] (base case)\n └── [10] (base case)\n\nCOMBINE (merge) phase:\n[38] + [27] --> merge --> [27, 38]\n[43] + [3] --> merge --> [3, 43]\n[27, 38] + [3, 43] --> merge --> [3, 27, 38, 43]\n[9] + [82] --> merge --> [9, 82]\n[9, 82] + [10] --> merge --> [9, 10, 82]\n[3, 27, 38, 43] + [9, 10, 82] --> merge --> [3, 9, 10, 27, 38, 43, 82]\n```\n\n\nLet us look at how the merge of `[27, 38]` and `[3, 43]` works in detail:\n\n\n```shell\nLeft: [27, 38] Right: [3, 43]\ni = 0, j = 0\n\nStep 1: Compare 27 vs 3. 3 < 27, pick 3. Result: [3] j = 1\nStep 2: Compare 27 vs 43. 27 < 43, pick 27. Result: [3, 27] i = 1\nStep 3: Compare 38 vs 43. 38 < 43, pick 38. Result: [3, 27, 38] i = 2\nStep 4: Left exhausted. Copy remaining: 43. Result: [3, 27, 38, 43]\n```\n\n\nThe following diagram shows how the array is split apart and then merged back together:\n\n\n```mermaid\nflowchart TD\n A[\"[38, 27, 43, 3, 9, 82, 10]\"]\n\n A --> B[\"[38, 27, 43, 3]\"]\n A --> C[\"[9, 82, 10]\"]\n\n B --> D[\"[38, 27]\"]\n B --> E[\"[43, 3]\"]\n\n C --> F[\"[9, 82]\"]\n C --> G[\"[10]\"]\n\n D --> D1[\"[38]\"]\n D --> D2[\"[27]\"]\n E --> E1[\"[43]\"]\n E --> E2[\"[3]\"]\n F --> F1[\"[9]\"]\n F --> F2[\"[82]\"]\n\n D1 --> M1[\"[27, 38]\"]\n D2 --> M1\n E1 --> M2[\"[3, 43]\"]\n E2 --> M2\n\n F1 --> M3[\"[9, 82]\"]\n F2 --> M3\n G --> M4[\"[9, 10, 82]\"]\n M3 --> M4\n\n M1 --> M5[\"[3, 27, 38, 43]\"]\n M2 --> M5\n\n M5 --> M6[\"[3, 9, 10, 27, 38, 43, 82]\"]\n M4 --> M6\n\n style A fill:#00ceff,stroke:#000,color:#000\n style B fill:#ffa94d,stroke:#000,color:#000\n style C fill:#ffa94d,stroke:#000,color:#000\n style D fill:#38d9a9,stroke:#000,color:#000\n style E fill:#38d9a9,stroke:#000,color:#000\n style F fill:#38d9a9,stroke:#000,color:#000\n style G fill:#38d9a9,stroke:#000,color:#000\n style D1 fill:#69db7c,stroke:#000,color:#000\n style D2 fill:#69db7c,stroke:#000,color:#000\n style E1 fill:#69db7c,stroke:#000,color:#000\n style E2 fill:#69db7c,stroke:#000,color:#000\n style F1 fill:#69db7c,stroke:#000,color:#000\n style F2 fill:#69db7c,stroke:#000,color:#000\n style M1 fill:#ffa94d,stroke:#000,color:#000\n style M2 fill:#ffa94d,stroke:#000,color:#000\n style M3 fill:#ffa94d,stroke:#000,color:#000\n style M4 fill:#ffa94d,stroke:#000,color:#000\n style M5 fill:#00ceff,stroke:#000,color:#000\n style M6 fill:#00ceff,stroke:#000,color:#000\n```\n\n\n### Complexity Analysis\n\n- **Time Complexity: O(n log n)**. At each level of recursion, we do O(n) work total (every element participates in exactly one merge at each level). There are log(n) levels because we halve the array each time. So total work = O(n) * O(log n) = O(n log n). This holds for the best, average, and worst case.\n- **Space Complexity: O(n)**. We need temporary arrays during the merge step. At any point in the recursion, the temporary arrays together hold at most n elements. The recursion stack adds O(log n), but that is dominated by the O(n) merge space.\n\n---\n\n# When to Use Divide and Conquer\n\nDivide and conquer is powerful, but it is not the right tool for every problem. Here are the characteristics that make a problem a good fit:\n\n\n| Characteristic | Why It Matters |\n|---------------|----------------|\n| Problem can be split into independent subproblems | Subproblems can be solved without depending on each other |\n| Subproblems are the same type as the original | Recursion works naturally |\n| An efficient combine step exists | Without it, splitting gives no benefit |\n| Roughly equal splits are possible | Balanced splits give O(log n) levels |\n\n\n### Problem Types That Fit Divide and Conquer\n\n- **Sorting**: Merge sort, quick sort\n- **Searching**: Binary search, finding k-th smallest element\n- **Computational geometry**: Closest pair of points, convex hull\n- **Arithmetic**: Large number multiplication, matrix multiplication, fast Fourier transform\n- **Tree/array problems**: Maximum subarray, count inversions\n\n### When NOT to Use Divide and Conquer\n\nThere are situations where divide and conquer is the wrong approach:\n\n- **Subproblems overlap.** If solving one subproblem requires information from another, you need dynamic programming instead (more on this below).\n- **No efficient combine step.** If merging results is as expensive as solving the original problem, you gain nothing from splitting.\n- **The problem is already linear.** If you can solve it in O(n) with a single pass (like finding the max), divide and conquer adds overhead without benefit. The recursion call stack and extra divisions make it slower in practice.\n- **Small input sizes.** The overhead of recursive calls, splitting, and merging makes divide and conquer slower than brute force for small inputs. This is why practical implementations switch to insertion sort for small subarrays (typically n < 10-20).\n\n---\n\n# Divide and Conquer vs Dynamic Programming\n\nThis is one of the most common interview questions, and the confusion is understandable. Both techniques break problems into subproblems and solve them recursively. The key difference comes down to one question: **do the subproblems overlap?**\n\n### The Core Difference\n\nIn divide and conquer, the subproblems are **independent**. When you split an array for merge sort, the left half and right half share no elements. Solving one gives you no information about the other.\n\nIn dynamic programming, the subproblems **overlap**. When computing the Fibonacci number F(5), you need F(4) and F(3). But computing F(4) also needs F(3). The subproblem F(3) appears multiple times. If you solve it from scratch each time, you waste work. Dynamic programming avoids this by storing (memoizing) results.\n\n\n```mermaid\nflowchart TD\n subgraph DC[\"Divide and Conquer
(Independent Subproblems)\"]\n A1[\"Problem\"] --> B1[\"Sub A\"]\n A1 --> C1[\"Sub B\"]\n B1 --> D1[\"Sub A1\"]\n B1 --> E1[\"Sub A2\"]\n C1 --> F1[\"Sub B1\"]\n C1 --> G1[\"Sub B2\"]\n end\n\n subgraph DP[\"Dynamic Programming
(Overlapping Subproblems)\"]\n A2[\"F(5)\"] --> B2[\"F(4)\"]\n A2 --> C2[\"F(3)\"]\n B2 --> D2[\"F(3)\"]\n B2 --> E2[\"F(2)\"]\n C2 --> F2[\"F(2)\"]\n C2 --> G2[\"F(1)\"]\n end\n\n style A1 fill:#00ceff,stroke:#000,color:#000\n style B1 fill:#ffa94d,stroke:#000,color:#000\n style C1 fill:#ffa94d,stroke:#000,color:#000\n style D1 fill:#38d9a9,stroke:#000,color:#000\n style E1 fill:#38d9a9,stroke:#000,color:#000\n style F1 fill:#38d9a9,stroke:#000,color:#000\n style G1 fill:#38d9a9,stroke:#000,color:#000\n style A2 fill:#00ceff,stroke:#000,color:#000\n style B2 fill:#ffa94d,stroke:#000,color:#000\n style C2 fill:#ffa94d,stroke:#000,color:#000\n style D2 fill:#ff8787,stroke:#000,color:#000\n style E2 fill:#38d9a9,stroke:#000,color:#000\n style F2 fill:#ff8787,stroke:#000,color:#000\n style G2 fill:#38d9a9,stroke:#000,color:#000\n```\n\n\nIn the divide and conquer tree (left), every subproblem is unique. In the dynamic programming tree (right), the red nodes show subproblems that appear more than once. F(3) and F(2) are computed multiple times unless we cache their results.\n\n### Comparison Table\n\n\n| Aspect | Divide and Conquer | Dynamic Programming |\n|--------|-------------------|---------------------|\n| Subproblems | Independent, no overlap | Overlapping, repeated |\n| Approach | Top-down recursion | Top-down with memoization or bottom-up tabulation |\n| Storage | No caching needed | Caches subproblem results |\n| Combine step | Merges independent results | Builds from cached sub-results |\n| Examples | Merge sort, binary search, closest pair | Fibonacci, knapsack, longest common subsequence |\n| Time saved by | Reducing problem size efficiently | Avoiding redundant computation |\n\n\n### How to Tell Which to Use\n\nWhen you face a problem, ask:\n\n1. **Can I split it into independent parts?** If yes, think divide and conquer.\n2. **Will the same subproblem appear multiple times?** If yes, think dynamic programming.\n3. **Does the problem ask for an optimal value (min/max/count)?** Usually DP.\n4. **Does the problem involve sorting, searching, or geometric computation?** Often divide and conquer.\n\nSome problems can be solved with both. For example, computing the number of inversions in an array can use a modified merge sort (divide and conquer) or a DP/BIT approach. Choose the one that fits most naturally.\n\n---\n\n# Common Mistakes and How to Avoid Them\n\n### Mistake 1: Wrong Base Case\n\nThe most frequent bug in divide and conquer is getting the base case wrong. If you do not stop recursion at the right point, you either get infinite recursion or incorrect results.\n\n\n```java\n// WRONG: Missing base case leads to infinite recursion\npublic void mergeSort(int[] arr, int left, int right) {\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// CORRECT: Stop when subarray has 0 or 1 elements\npublic void mergeSort(int[] arr, int left, int right) {\n if (left >= right) {\n return; // Base case: nothing to sort\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```python\n# WRONG: Missing base case leads to infinite recursion\ndef mergeSort(arr, left, right):\n mid = left + (right - left) // 2\n mergeSort(arr, left, mid)\n mergeSort(arr, mid + 1, right)\n merge(arr, left, mid, right)\n\n# CORRECT: Stop when subarray has 0 or 1 elements\ndef mergeSort(arr, left, right):\n if left >= right:\n return # Base case: nothing to sort\n 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```cpp\n// WRONG: Missing base case leads to infinite recursion\nvoid mergeSort(int[] arr, int left, int right) {\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// CORRECT: Stop when subarray has 0 or 1 elements\nvoid mergeSort(int[] arr, int left, int right) {\n if (left >= right) {\n return; // Base case: nothing to sort\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\n// WRONG: Missing base case leads to infinite recursion\nfunc mergeSort(arr []int, left, right int) {\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\n// CORRECT: Stop when subarray has 0 or 1 elements\nfunc mergeSort(arr []int, left, right int) {\n\tif left >= right {\n\t\treturn // Base case: nothing to sort\n\t}\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```\n\n```csharp\n// WRONG: Missing base case leads to infinite recursion\npublic void mergeSort(int[] arr, int left, int right) {\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// CORRECT: Stop when subarray has 0 or 1 elements\npublic void mergeSort(int[] arr, int left, int right) {\n if (left >= right) {\n return; // Base case: nothing to sort\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```rust\n// WRONG: Missing base case leads to infinite recursion\nfn merge_sort(arr: &mut [i32], left: usize, right: usize) {\n let 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}\n\n// CORRECT: Stop when subarray has 0 or 1 elements\nfn merge_sort(arr: &mut [i32], left: usize, right: usize) {\n if left >= right {\n return; // Base case: nothing to sort\n }\n let 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}\n```\n\n```javascript\n// WRONG: Missing base case leads to infinite recursion\nfunction mergeSort(arr, left, right) {\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\n// CORRECT: Stop when subarray has 0 or 1 elements\nfunction mergeSort(arr, left, right) {\n if (left >= right) {\n return; // Base case: nothing to sort\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```\n\n```typescript\n// WRONG: Missing base case leads to infinite recursion\nfunction mergeSort(arr: number[], left: number, right: number): void {\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\n// CORRECT: Stop when subarray has 0 or 1 elements\nfunction mergeSort(arr: number[], left: number, right: number): void {\n if (left >= right) {\n return; // Base case: nothing to sort\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```\n\n\n### Mistake 2: Inefficient Merge Step\n\nAllocating new arrays inside every merge call is a common performance trap. For competitive programming and interviews, it is acceptable, but for production code, pre-allocating a single auxiliary array is much better.\n\n\n```java\n// LESS EFFICIENT: New arrays allocated in every merge call\nprivate void merge(int[] arr, int left, int mid, int right) {\n int[] leftArr = new int[mid - left + 1]; // Allocation here\n int[] rightArr = new int[right - mid]; // And here\n // ... merge logic\n}\n\n// MORE EFFICIENT: Use a pre-allocated auxiliary array\nprivate int[] aux; // Allocated once in the initial call\n\npublic void mergeSort(int[] arr) {\n aux = new int[arr.length]; // One allocation\n mergeSort(arr, 0, arr.length - 1);\n}\n\nprivate void merge(int[] arr, int left, int mid, int right) {\n for (int k = left; k <= right; k++) {\n aux[k] = arr[k]; // Copy to pre-allocated array\n }\n // ... merge using aux array\n}\n```\n\n```python\n# LESS EFFICIENT: New arrays allocated in every merge call\ndef merge(arr, left, mid, right):\n left_arr = [0] * (mid - left + 1) # Allocation here\n right_arr = [0] * (right - mid) # And here\n # ... merge logic\n\n# MORE EFFICIENT: Use a pre-allocated auxiliary array\naux = None # Allocated once in the initial call\n\ndef mergeSort(arr):\n global aux\n aux = [0] * len(arr) # One allocation\n mergeSort(arr, 0, len(arr) - 1)\n\ndef merge(arr, left, mid, right):\n for k in range(left, right + 1):\n aux[k] = arr[k] # Copy to pre-allocated array\n # ... merge using aux array\n```\n\n```cpp\n// LESS EFFICIENT: New arrays allocated in every merge call\nvoid merge(vector& arr, int left, int mid, int right) {\n vector leftArr(mid - left + 1); // Allocation here\n vector rightArr(right - mid); // And here\n // ... merge logic\n}\n\n// MORE EFFICIENT: Use a pre-allocated auxiliary array\nvector aux; // Allocated once in the initial call\n\nvoid mergeSort(vector& arr) {\n aux = vector(arr.size()); // One allocation\n mergeSort(arr, 0, (int)arr.size() - 1);\n}\n\nvoid merge(vector& arr, int left, int mid, int right) {\n for (int k = left; k <= right; k++) {\n aux[k] = arr[k]; // Copy to pre-allocated array\n }\n // ... merge using aux array\n}\n```\n\n```go\n// LESS EFFICIENT: New arrays allocated in every merge call\nfunc merge(arr []int, left, mid, right int) {\n\tleftArr := make([]int, mid-left+1) // Allocation here\n\trightArr := make([]int, right-mid) // And here\n\t_ = leftArr\n\t_ = rightArr\n\t// ... merge logic\n}\n\n// MORE EFFICIENT: Use a pre-allocated auxiliary array\nvar aux []int // Allocated once in the initial call\n\nfunc mergeSort(arr []int) {\n\taux = make([]int, len(arr)) // One allocation\n\tmergeSort(arr, 0, len(arr)-1)\n}\n\nfunc merge(arr []int, left, mid, right int) {\n\tfor k := left; k <= right; k++ {\n\t\taux[k] = arr[k] // Copy to pre-allocated array\n\t}\n\t// ... merge using aux array\n}\n```\n\n```csharp\n// LESS EFFICIENT: New arrays allocated in every merge call\nprivate void Merge(int[] arr, int left, int mid, int right) {\n int[] leftArr = new int[mid - left + 1]; // Allocation here\n int[] rightArr = new int[right - mid]; // And here\n // ... merge logic\n}\n\n// MORE EFFICIENT: Use a pre-allocated auxiliary array\nprivate int[] aux; // Allocated once in the initial call\n\npublic void MergeSort(int[] arr) {\n aux = new int[arr.Length]; // One allocation\n MergeSort(arr, 0, arr.Length - 1);\n}\n\nprivate void Merge(int[] arr, int left, int mid, int right) {\n for (int k = left; k <= right; k++) {\n aux[k] = arr[k]; // Copy to pre-allocated array\n }\n // ... merge using aux array\n}\n```\n\n```rust\n// LESS EFFICIENT: New arrays allocated in every merge call\nfn merge(arr: &mut [i32], left: usize, mid: usize, right: usize) {\n let left_arr = vec![0; mid - left + 1]; // Allocation here\n let right_arr = vec![0; right - mid]; // And here\n let _ = left_arr;\n let _ = right_arr;\n // ... merge logic\n}\n\n// MORE EFFICIENT: Use a pre-allocated auxiliary array\nstatic mut AUX: Vec = Vec::new(); // Allocated once in the initial call\n\nfn merge_sort(arr: &mut [i32]) {\n unsafe {\n AUX = vec![0; arr.len()]; // One allocation\n }\n merge_sort_rec(arr, 0, arr.len().saturating_sub(1));\n}\n\nfn merge_sort_rec(arr: &mut [i32], left: usize, right: usize) {\n if left >= right {\n return;\n }\n let mid = left + (right - left) / 2;\n merge_sort_rec(arr, left, mid);\n merge_sort_rec(arr, mid + 1, right);\n merge(arr, left, mid, right);\n}\n\nfn merge(arr: &mut [i32], left: usize, mid: usize, right: usize) {\n unsafe {\n for k in left..=right {\n AUX[k] = arr[k]; // Copy to pre-allocated array\n }\n }\n // ... merge using aux array\n}\n```\n\n```javascript\n// LESS EFFICIENT: New arrays allocated in every merge call\nfunction merge(arr, left, mid, right) {\n const leftArr = new Array(mid - left + 1); // Allocation here\n const rightArr = new Array(right - mid); // And here\n // ... merge logic\n}\n\n// MORE EFFICIENT: Use a pre-allocated auxiliary array\nlet aux = null; // Allocated once in the initial call\n\nfunction mergeSort(arr) {\n aux = new Array(arr.length); // One allocation\n mergeSort(arr, 0, arr.length - 1);\n}\n\nfunction merge(arr, left, mid, right) {\n for (let k = left; k <= right; k++) {\n aux[k] = arr[k]; // Copy to pre-allocated array\n }\n // ... merge using aux array\n}\n```\n\n```typescript\n// LESS EFFICIENT: New arrays allocated in every merge call\nprivate merge(arr: number[], left: number, mid: number, right: number): void {\n const leftArr = new Array(mid - left + 1); // Allocation here\n const rightArr = new Array(right - mid); // And here\n // ... merge logic\n}\n\n// MORE EFFICIENT: Use a pre-allocated auxiliary array\nprivate aux!: number[]; // Allocated once in the initial call\n\npublic mergeSort(arr: number[]): void {\n this.aux = new Array(arr.length); // One allocation\n this.mergeSort(arr, 0, arr.length - 1);\n}\n\nprivate merge(arr: number[], left: number, mid: number, right: number): void {\n for (let k = left; k <= right; k++) {\n this.aux[k] = arr[k]; // Copy to pre-allocated array\n }\n // ... merge using aux array\n}\n```\n\n\n### Mistake 3: Integer Overflow in Midpoint Calculation\n\nThis is a subtle but important bug. If `left` and `right` are both large, their sum can overflow.\n\n\n```java\n// WRONG: Can overflow if left + right > Integer.MAX_VALUE\nint mid = (left + right) / 2;\n\n// CORRECT: Avoids overflow\nint mid = left + (right - left) / 2;\n```\n\n```python\n# WRONG: Can overflow if left + right > Integer.MAX_VALUE\nmid = (left + right) // 2\n\n# CORRECT: Avoids overflow\nmid = left + (right - left) // 2\n```\n\n```cpp\n// WRONG: Can overflow if left + right > std::numeric_limits::max()\nint mid = (left + right) / 2;\n\n// CORRECT: Avoids overflow\nint mid = left + (right - left) / 2;\n```\n\n```go\n// WRONG: Can overflow if left + right > math.MaxInt\nmid := (left + right) / 2\n\n// CORRECT: Avoids overflow\nmid := left + (right-left)/2\n```\n\n```csharp\n// WRONG: Can overflow if left + right > int.MaxValue\nint mid = (left + right) / 2;\n\n// CORRECT: Avoids overflow\nint mid = left + (right - left) / 2;\n```\n\n```rust\n// WRONG: Can overflow if left + right > i32::MAX\nlet mid = (left + right) / 2;\n\n// CORRECT: Avoids overflow\nlet mid = left + (right - left) / 2;\n```\n\n```javascript\n// WRONG: Can overflow if left + right > Number.MAX_SAFE_INTEGER\nconst mid = Math.floor((left + right) / 2);\n\n// CORRECT: Avoids overflow\nconst mid = left + Math.floor((right - left) / 2);\n```\n\n```typescript\n// WRONG: Can overflow if left + right > Number.MAX_SAFE_INTEGER\nconst mid = Math.floor((left + right) / 2);\n\n// CORRECT: Avoids overflow\nconst mid = left + Math.floor((right - left) / 2);\n```\n\n\n### Mistake 4: Not Handling Unequal Splits\n\nWhen the array length is odd, the two halves will differ in size by one. Your code must handle this gracefully.\n\n\n```java\n// WRONG: Assumes even-length arrays\nint mid = left + (right - left) / 2;\nmergeSort(arr, left, mid - 1); // Could miss elements\nmergeSort(arr, mid, right);\n\n// CORRECT: Left half includes mid\nint mid = left + (right - left) / 2;\nmergeSort(arr, left, mid); // Left half: [left, mid]\nmergeSort(arr, mid + 1, right); // Right half: [mid+1, right]\n```\n\n```python\n# WRONG: Assumes even-length arrays\nmid = left + (right - left) // 2\nmergeSort(arr, left, mid - 1) # Could miss elements\nmergeSort(arr, mid, right)\n\n# CORRECT: Left half includes mid\nmid = left + (right - left) // 2\nmergeSort(arr, left, mid) # Left half: [left, mid]\nmergeSort(arr, mid + 1, right) # Right half: [mid+1, right]\n```\n\n```cpp\n// WRONG: Assumes even-length arrays\nint mid = left + (right - left) / 2;\nmergeSort(arr, left, mid - 1); // Could miss elements\nmergeSort(arr, mid, right);\n\n// CORRECT: Left half includes mid\nmid = left + (right - left) / 2;\nmergeSort(arr, left, mid); // Left half: [left, mid]\nmergeSort(arr, mid + 1, right); // Right half: [mid+1, right]\n```\n\n```go\n// WRONG: Assumes even-length arrays\nmid := left + (right-left)/2\nmergeSort(arr, left, mid-1) // Could miss elements\nmergeSort(arr, mid, right)\n\n// CORRECT: Left half includes mid\nmid = left + (right-left)/2\nmergeSort(arr, left, mid) // Left half: [left, mid]\nmergeSort(arr, mid+1, right) // Right half: [mid+1, right]\n```\n\n```csharp\n// WRONG: Assumes even-length arrays\nint mid = left + (right - left) / 2;\nmergeSort(arr, left, mid - 1); // Could miss elements\nmergeSort(arr, mid, right);\n\n// CORRECT: Left half includes mid\nmid = left + (right - left) / 2;\nmergeSort(arr, left, mid); // Left half: [left, mid]\nmergeSort(arr, mid + 1, right); // Right half: [mid+1, right]\n```\n\n```rust\n// WRONG: Assumes even-length arrays\nlet mid = left + (right - left) / 2;\nmergeSort(arr, left, mid - 1); // Could miss elements\nmergeSort(arr, mid, right);\n\n// CORRECT: Left half includes mid\nlet mid = left + (right - left) / 2;\nmergeSort(arr, left, mid); // Left half: [left, mid]\nmergeSort(arr, mid + 1, right); // Right half: [mid+1, right]\n```\n\n```javascript\n// WRONG: Assumes even-length arrays\nlet mid = left + Math.floor((right - left) / 2);\nmergeSort(arr, left, mid - 1); // Could miss elements\nmergeSort(arr, mid, right);\n\n// CORRECT: Left half includes mid\nmid = left + Math.floor((right - left) / 2);\nmergeSort(arr, left, mid); // Left half: [left, mid]\nmergeSort(arr, mid + 1, right); // Right half: [mid+1, right]\n```\n\n```typescript\n// WRONG: Assumes even-length arrays\nlet mid = left + Math.floor((right - left) / 2);\nmergeSort(arr, left, mid - 1); // Could miss elements\nmergeSort(arr, mid, right);\n\n// CORRECT: Left half includes mid\nmid = left + Math.floor((right - left) / 2);\nmergeSort(arr, left, mid); // Left half: [left, mid]\nmergeSort(arr, mid + 1, right); // Right half: [mid+1, right]\n```\n\n\n### Mistake 5: Confusing When to Divide and Conquer vs Brute Force\n\nNot every problem benefits from divide and conquer. If you find yourself writing a divide and conquer solution where the combine step is as expensive as the original problem, step back and reconsider. A common sign is when your \"optimized\" solution has the same complexity as the brute force but with more overhead.","pageType":"dsa"}

Divide and Conquer

Ashish Pratap Singh

Get Premium