CHAPTER 02 · Divide & Conquer

Divide and conquer

Divide and conquer is one idea: cut a large problem into smaller problems of the same shape, let the recursion solve each one, then combine the sub-answers into the final answer. The introduction chapter asked you to trust recursion. This is the first chapter where that trust pays off. You will see a slow O(n) or O(n²) method become O(n log n), and sometimes O(log n), only because the input is cut in half at every step.

§01

Three steps: divide, conquer, combine

Recursion is a way to write code. Divide and conquer is a way to design a solution.

Start with a simple picture. You have a stack of 1000 ballots to count. One person counting alone takes all day. A faster way: split the stack into 10 smaller stacks and give one stack to each of 10 people. Each person may split their stack again. At the end, add the 10 subtotals together. That is divide and conquer: cut the problem into smaller problems of the same shape, solve them separately, then combine the results.

How is this different from plain recursion? Recursion is the language feature that lets a function call itself. Divide and conquer is a strategy that uses recursion to solve a problem, and it is the most common one. Every divide and conquer solution has the same three steps.

Divide

Cut a problem of size n into several smaller problems of the same kind, usually two problems of size n/2. Every piece must be strictly smaller than the original, otherwise the recursion never reaches the base case. The pieces must also not overlap: they share no work, so each one is solved exactly once.

Conquer

Solve each subproblem by recursion. When a subproblem is small enough to answer directly, such as a single element, return the answer at once. That case is the base case. Here you use the idea from the introduction chapter: trust the recursion to return a correct sub-answer, and do not trace the calls in your head.

Combine

Assemble the sub-answers into the answer for the original problem. This step decides almost everything: how hard the problem is to solve, and what the final time complexity turns out to be.

In code the three steps become a fixed skeleton. The example below is merge sort. Sorting is the classic first use of divide and conquer. Chapter 01 covers its stability and its in-place version; here it only shows the skeleton.

merge_sort_template.py

1class Solution:

2 def sortArray(self, a: list[int]) -> list[int]:

3 if len(a) <= 1:

4 return a # conquer: base case

5 mid = len(a) // 2 # divide: cut in half

6 left = self.sortArray(a[:mid])

7 right = self.sortArray(a[mid:])

8 return self._merge(left, right) # combine: merge two sorted halves

10 def _merge(self, x: list[int], y: list[int]) -> list[int]:

11 out, i, j = [], 0, 0

12 while i < len(x) and j < len(y):

13 if x[i] <= y[j]:

14 out.append(x[i]); i += 1

15 else:

16 out.append(y[j]); j += 1

17 out.extend(x[i:]); out.extend(y[j:])

18 return out

A slice such as a[:mid] copies the elements every time. That is easy to read but it costs extra time and memory. A common alternative is to pass the index range (lo, hi) and read the original list in place.

Three properties of merge sort are worth fixing in your memory now, because they come back in every sorting question. Its time is O(n log n) in the best, the average, and the worst case, because the split is always down the middle and never depends on the values. It needs O(n) auxiliary space for the output buffer, plus O(log n) for the call stack. And it is stable: equal values keep their original order, because the merge takes from the left half on a tie. That is what <= is doing in the code above.

Why is divide and conquer correct? Induction

A divide and conquer solution is proved correct by induction, the same method used for recursion. Step one: the base case is correct. A single element is already sorted, so that is true. Step two: the inductive step is correct. Assume the recursive calls sort the left half and the right half correctly. If merge turns two sorted arrays into one sorted array, the whole array is sorted. Both steps hold, so the result holds for every input size. You only ever have to prove the combine step. The recursive part is covered by the inductive assumption. That is the reason you are allowed to trust the recursion.

Two common beginner mistakes

1. The subproblem does not get smaller. If the divide step produces one empty part and one part the same size as the input, the recursion never ends and the call stack overflows. Every call must move closer to the base case. 2. The base case is missing or wrong. If you forget the length <= 1 exit, or write the condition incorrectly, the recursion also never ends. The rule from the introduction chapter still applies: write the exit first, then write the recursive calls.

In practice: divide and conquer scales computation

MapReduce (from Google), Hadoop, and Spark all use this structure. They split a large dataset into pieces, send the pieces to many machines that each compute a partial result (map), and then combine the partial results (reduce). When the data does not fit in memory, external merge sort splits the file into blocks that do fit, sorts each block, and merges the sorted blocks. That is the same merge step, applied to files instead of arrays. Divide and conquer matters because it is also the standard way to describe work that can run in parallel.

§02

The recursion tree: work per level × number of levels

You can count the cost of a divide and conquer algorithm without memorizing any formula.

Almost every divide and conquer running time can be written as a recurrence. Read it as: the original problem costs a subproblems of size n/b, plus f(n) for the divide and combine steps.

T(n) = a · T(n/b) + f(n)

Merge sort is T(n) = 2·T(n/2) + O(n): two halves, and one linear pass to merge them. Rather than memorizing a formula, draw the recursion as a tree and count two numbers.

Merge sort: every level touches all n elements, and there are log n levels

1258

3479

12345789

Divide first: halve the array again and again until every piece holds one element. A single element is already sorted, so the real work all happens on the way back up.

1 / 4

Look at the levels in the animation. The merging work on each level adds up to O(n): level 1 does four merges that produce runs of 2, level 2 does two merges that produce runs of 4, and level 3 does one merge of 8. The number of elements never changes, so each level costs O(n). The number of levels is the number of times n can be halved down to 1, which is log₂n. Multiply the two numbers: O(n) × log n = O(n log n). No formula needed.

The same counting handles most of the recurrences you will meet:

Recurrence	Work per level	Levels	Result	Example
`T(n)=2T(n/2)+O(n)`	O(n), the same on every level	log n	O(n log n)	Merge sort, LC 23
`T(n)=2T(n/2)+O(1)`	Grows downward, the leaves dominate	log n	O(n)	Visiting every node of a full binary tree
`T(n)=T(n/2)+O(1)`	O(1)	log n	O(log n)	Binary search, fast power
`T(n)=T(n/2)+O(n)`	Shrinks downward, the root dominates	log n	O(n)	Quickselect (expected)

The pattern behind the table is one question: is the work concentrated at the root, spread evenly, or concentrated at the leaves? Evenly spread costs one extra factor of log n. Root-heavy follows the root. Leaf-heavy follows the number of leaves. The Master theorem is the exact version of that question.

The Master theorem, stated exactly

For T(n) = a·T(n/b) + f(n) with a ≥ 1 and b > 1, compare f(n), the cost of dividing and combining, with n^(log_b a), which is how many leaves the tree has.

Case 1. f(n) is polynomially smaller, that is f(n) = O(n^(log_b a − ε)) for some ε > 0. The leaves dominate and T(n) = Θ(n^(log_b a)).
Case 2. The two have the same order, f(n) = Θ(n^(log_b a)). Every level costs the same and T(n) = Θ(n^(log_b a) · log n).
Case 3. f(n) is polynomially larger, f(n) = Ω(n^(log_b a + ε)) for some ε > 0, and the regularity condition a·f(n/b) ≤ c·f(n) holds for some constant c < 1 and all large enough n. Then the root dominates and T(n) = Θ(f(n)).

Two things are easy to get wrong. The regularity condition in case 3 is not optional: without it the root cost may not shrink fast enough going down, and the sum is no longer Θ(f(n)). And the three cases do not cover every recurrence — there are gaps between them. T(n) = 2T(n/2) + n log n is one: here n^(log_b a) = n and f(n) = n log n is larger than n but not polynomially larger, so no case applies. Its answer, Θ(n log²n), has to come from the recursion tree. That is why the picture is worth more than the formula.

How to answer a complexity question in an interview

When the interviewer asks how fast your divide and conquer solution is, do not jump straight to the answer. Say this instead: "I write the recurrence T(n) = a·T(n/b) + f(n) and draw the recursion tree. The root costs f(n), there are about log_b n levels, and the tree has n^(log_b a) leaves. Comparing those two tells me which side dominates, so..." Deriving it on the spot is safer than reciting a result, and it shows where the number comes from. This one method covers every divide and conquer problem in the chapter.

§03

Worked example A · LC 50 Pow(x, n): from n multiplications to log n

MEDIUM

The first big win of divide and conquer: the exponent is halved at every step.

Problem: compute x raised to the power n. Brute force: a loop that multiplies n times, O(n). When n is near 2³¹ that is more than two billion multiplications, too slow to pass. How can it be faster? To get x⁸, instead of multiplying x by itself eight times, compute x² = x·x, then x⁴ = (x²)², then x⁸ = (x⁴)². Each squaring doubles the exponent, so three squarings reach x⁸. Going from exponent 8 down to 1 takes log₂8 = 3 steps.

This is divide and conquer: x^n = (x^(n/2))². If n is even, square directly. If n is odd, x^n = (x^(n/2))² · x, adding back the single x that integer division dropped. Here is 3¹³ being cut down and combined back up:

Fast power 3¹³: the exponent halves every level, so there are only log n levels

The goal is 3¹³. A plain loop multiplies 13 times. Divide and conquer asks one question first: can 13 be cut in half? 13 = 6×2 + 1, so 3¹³ = (3⁶)² × 3. Compute 3⁶ first.

1 / 9

Notice that this "tree" is really a chain. Each call produces one subproblem, x^(n/2), not two. So there are log n levels with O(1) work on each: O(log n) time and O(log n) stack. Binary search has the same shape — it splits the range in two, but only one half survives, so it is O(log n) and not O(n log n). Merge sort keeps both halves, and that is exactly why it costs O(n log n) instead.

lc50_fast_pow_recursive.py

1class Solution:

2 def myPow(self, x: float, n: int) -> float:

3 if n < 0:

4 x, n = 1 / x, -n # Python ints are unbounded, negating is safe

5 def fast(n: int) -> float:

6 if n == 0:

7 return 1.0 # base case

8 half = fast(n // 2) # compute it ONCE

9 sq = half * half

10 return sq * x if n & 1 else sq # n & 1 tests the lowest bit

11 return fast(n)

Python integers have unlimited precision, so the overflow trap does not exist here and a negative exponent can be negated directly. n & 1 reads the lowest bit to test odd or even; it is more common than n % 2 in this kind of code (the bit manipulation chapter covers it).

The recursive version is clear, but it costs O(log n) stack. Production code usually prefers the iterative version. Write n in binary and scan from the lowest bit upward. Whenever a bit is 1, multiply the value belonging to that bit position into the result. It is the same computation with no stack at all:

lc50_fast_pow_iterative.py

1class Solution:

2 def myPow(self, x: float, n: int) -> float:

3 if n < 0:

4 x, n = 1 / x, -n

5 res = 1.0

6 while n:

7 if n & 1:

8 res *= x # this bit is 1

9 x *= x # x -> x^2, x^4, x^8...

10 n >>= 1

11 return res

In Python while n: means while n != 0. This version has no recursion, so the recursion depth limit never applies. It is the safest choice for very large exponents.

Complexity and follow-up questions

Time O(log n). Space O(log n) for the recursive version and O(1) for the iterative one. Three follow-ups come up often. 1. "What if the answer must be taken modulo a large prime?" Take the modulus after every multiplication. That is modular exponentiation, the core of RSA and of many counting problems (the maths chapter covers it). 2. "Compute the 10¹⁸-th Fibonacci number." Use matrix fast power: write the recurrence as a matrix product and apply fast power to the matrix, which needs O(log n) matrix multiplications. 3. "Why can you not compute x^(n/2) twice?" Because the recursion tree becomes full again and the time returns to O(n).

In practice: every HTTPS handshake runs fast power

Public key cryptography such as RSA and Diffie-Hellman is built on modular exponentiation, a^b mod m, where b has hundreds or thousands of bits. Multiplying one step at a time would take about 2^2048 multiplications for a 2048-bit exponent, which no machine can finish. Fast power needs about 2048 squarings, plus at most one extra multiplication per bit. The lock icon in your address bar rests on these few lines of divide and conquer.

§04

Worked example B · LC 23 Merge k Sorted Lists: merge in pairs

HARD

Merging moves from arrays to linked lists, and pairing saves a whole factor.

Problem: given k sorted linked lists, merge them into one sorted list. Let N be the total number of nodes. Brute force (one list at a time): take the first list as the base, merge the second into it, then the third, and so on. The problem is that the base list grows with every merge: merge number i walks about the first i lists in full, and the sum is O(k·N). The idea: merging two lists costs only the total length of those two lists, so reduce the number of merges. Merging in pairs does exactly that:

LC 23: merge in pairs, so k lists become one in log k rounds

1→4→5

1→3→4

2→6

3→7

1→1→3→4→4→5

2→3→6→7

1→1→2→3→3→4→4→5→6→7

Four sorted lists. The naive method takes the first list and merges the other three into it one at a time. That base list keeps growing, so the total cost is O(k·N).

1 / 3

Compare the two methods. Merging one at a time needs k rounds and the base list keeps growing. Merging in pairs halves the number of lists each round, so it needs only log₂k rounds, and within a round every one of the N nodes is compared and moved exactly once (O(N) per level). Multiply the two numbers: O(N log k), plus O(log k) stack for the recursion. With k = 10000, log₂k ≈ 13, three orders of magnitude below k.

lc23_merge_k_lists.py

1class Solution:

2 def mergeKLists(self, lists: list[ListNode]) -> ListNode:

3 if not lists:

4 return None

6 def merge(lo: int, hi: int) -> ListNode:

7 if lo == hi:

8 return lists[lo] # base case: one list left

9 mid = (lo + hi) // 2 # divide

10 l, r = merge(lo, mid), merge(mid + 1, hi) # conquer

11 return merge_two(l, r) # combine

13 def merge_two(a, b):

14 dummy = tail = ListNode()

15 while a and b:

16 if a.val <= b.val:

17 tail.next, a = a, a.next

18 else:

19 tail.next, b = b, b.next

20 tail = tail.next

21 tail.next = a or b # attach whichever list is left

22 return dummy.next

24 return merge(0, len(lists) - 1)

tail.next = a or b uses Python short-circuiting: it takes a when a is not empty, otherwise b. The nested function closes over lists, so it does not have to be passed down.

Complexity and follow-up: merging against a priority queue

The divide and conquer solution runs in O(N log k) time with O(log k) stack. The usual follow-up is "is there another solution?" Yes: a priority queue (min-heap). Put the head node of each of the k lists into the heap, pop the smallest, append it to the result, and push its successor. That is also O(N log k). Both are accepted answers. The difference is that the heap needs O(k) extra space and has a larger constant factor, but it works when the lists arrive as streams instead of all at once. Heaps are the main topic of DataData chapter 09; here you get the divide and conquer route to the same bound.

In practice: multi-way merging in databases and log systems

An LSM-tree, the storage engine behind LevelDB, RocksDB, and Cassandra, continuously merges many small sorted files into larger ones in the background. A distributed system merges the sorted result streams returned by k machines into one globally sorted stream. Both are LC 23 at production scale. The only difference is that with billions of records they use a k-way heap merge, combining all k streams at once instead of two at a time.

§05

Worked example C · LC 53 Maximum Subarray: the divide and conquer view

MEDIUM

One problem, two methods: O(n log n) here, against Kadane's O(n) in chapter 07.

Problem: given an integer array, find the contiguous subarray with the largest sum and return that sum. Brute force: try every range, O(n²). The divide and conquer idea: cut once in the middle. The best subarray then has exactly three mutually exclusive homes:

1. entirely in the left half — the left recursion returns it;
2. entirely in the right half — the right recursion returns it;
3. crossing the midpoint — neither recursion can see it, so it has to be computed here.

Take the maximum of the three. Cases 1 and 2 come from trusting the recursion, so the only real work is case 3. Case 3 has a useful property: such a subarray must contain the midpoint. So scan left from the midpoint for the largest sum of a segment that ends at the midpoint (the best suffix of the left half), then scan right for the largest sum of a segment that starts just after the midpoint (the best prefix of the right half), and add the two. Follow the scan:

LC 53 divide and conquer: the best sum that crosses the midpoint

mid

-20

-32

-14

-57

Divide and conquer cuts once: the midpoint is index 4. The best subarray has only three possible homes — entirely in the left half, entirely in the right half, or crossing the midpoint. The two halves go to the recursion. The crossing case is what has to be computed here.

1 / 11

lc53_max_subarray_divide.py

1class Solution:

2 def maxSubArray(self, nums: list[int]) -> int:

3 def dc(lo: int, hi: int) -> int:

4 if lo == hi:

5 return nums[lo] # base case: single element

6 mid = (lo + hi) // 2

7 left = dc(lo, mid) # 1. entirely on the left

8 right = dc(mid + 1, hi) # 2. entirely on the right

9 cross = cross_sum(lo, mid, hi) # 3. crossing the midpoint

10 return max(left, right, cross)

12 def cross_sum(lo: int, mid: int, hi: int) -> int:

13 s, best_l = 0, float("-inf")

14 for i in range(mid, lo - 1, -1): # left: best segment ending at mid

15 s += nums[i]

16 best_l = max(best_l, s)

17 s, best_r = 0, float("-inf")

18 for j in range(mid + 1, hi + 1): # right: best segment from mid+1

19 s += nums[j]

20 best_r = max(best_r, s)

21 return best_l + best_r

23 return dc(0, len(nums) - 1)

range(mid, lo - 1, -1) counts down from mid to lo; the end value has to be written as lo−1 because the end is exclusive. float("-inf") is negative infinity, so an all-negative array still gives the right answer.

Complexity O(n log n): the recurrence is T(n) = 2T(n/2) + O(n), the same as merge sort, with O(log n) stack. But this problem has a faster solution. Chapter 07 on dynamic programming gives the Kadane view: define dp[i] as the largest sum of a subarray ending at index i, and one linear scan gives O(n) time and O(1) space. Compare the two:

This chapter · divide and conquer

O(n log n)

Cut in half, compute the crossing segment separately, take the maximum of the three. The split is by position: the answer is on the left, on the right, or across the cut. Slower, but it exposes the structure that lets two ranges be combined.

Chapter 07 · DP / Kadane

O(n)

dp[i] = max(nums[i], dp[i−1] + nums[i]), updating the best value as you scan. The split is by time: at each position you only ask whether the piece before you is worth keeping. Faster, and it is the optimal solution here.

lc53_kadane_for_compare.py

1# For comparison: chapter 07 DP / Kadane, one pass, O(n)

2class Solution:

3 def maxSubArray(self, nums: list[int]) -> int:

4 cur = best = nums[0]

5 for x in nums[1:]:

6 cur = max(x, cur + x) # extend, or start again at x

7 best = max(best, cur)

8 return best

One transition line takes the problem from O(n log n) to O(n).

So what is the divide and conquer view good for?

Kadane is faster, so why learn the divide and conquer solution? Because the structure it exposes, that two neighboring ranges can be combined, is the basis of a segment tree. Suppose the problem changes to: answer many queries for the largest subarray sum inside an arbitrary range [l, r], with updates in between. One Kadane pass is no longer enough. The divide and conquer solution stores four values per range — the range sum, the largest prefix sum, the largest suffix sum, and the largest subarray sum inside the range. Those four values sit on each node of a segment tree and combine in O(1), which answers a query in O(log n). Two solutions to one problem lead to two different places: one to DP, one to segment trees.

§06

Merging can also count: inversions, and a faster multiplication

Divide and conquer is not only for sorting. The same merge measures how far an array is from sorted, and a different split makes multiplication faster.

An inversion is a pair of positions with i < j and nums[i] > nums[j]. The number of inversions measures how far an array is from sorted: a fully increasing array has 0, and a fully decreasing array of length n has n(n−1)/2, the maximum possible. Comparing every pair costs O(n²). But merge sort can count them during the merge, at no extra cost, so the total stays O(n log n). (On LeetCode China this is LCR 170.)

The trick appears when merging two sorted halves. When you take a smaller value out of the right half, every value still waiting in the left half is larger than it and sits before it, so all of them form an inversion with it. Add the count of remaining left-half values in one step, with no pair-by-pair comparison:

A by-product of merging: counting the inversions that cross the two halves

left

right

Merge sort can count inversions along the way. An inversion is a pair where an earlier value is larger than a later one. The left half [3, 5] and the right half [2, 4] are already sorted, so the merge only has to count the inversions that cross the two halves.

1 / 5

Why does this miss nothing and count nothing twice? Every inversion that crosses the two halves is settled exactly once, at the moment its right-hand value is taken out. Inversions inside a half were already counted by that half's own recursion, and the two halves do not overlap, so no pair is counted by both. Divide, conquer, and combine each do their part, which turns a by-product of sorting into the answer to a counting problem.

Inversions outside the exercise

Counting inversions is the standard way to measure how much two rankings disagree, known as the Kendall tau distance. A recommender system compares your stated preferences with its own ordering, judges in a competition compare their rankings, and bioinformatics compares the order of genes — all with the same count. It is also exactly the number of swaps a bubble sort performs, so "how unsorted is this array" has a precise numeric answer.

Karatsuba: a 23-year-old student disproved a conjectured limit

Multiplying two n-digit numbers the way you learned at school costs O(n²): every digit meets every digit. For a long time that was believed to be the limit. In 1960 Andrey Kolmogorov stated in a seminar that O(n²) could not be beaten. A week later Anatoly Karatsuba, a 23-year-old student in the audience, showed otherwise. Split each number into a high and a low half: x = a·10^m + b and y = c·10^m + d. The school method needs 4 products: ac, ad, bc, bd. Karatsuba noticed that 3 are enough. Compute ac, bd, and (a+b)(c+d); then the middle term comes out for nothing, because ad + bc = (a+b)(c+d) − ac − bd.

The recurrence changes from T(n) = 4T(n/2) + O(n) to T(n) = 3T(n/2) + O(n), and the time drops from O(n²) to O(n^log₂3) ≈ O(n¹·⁵⁸). That is the lesson of this chapter in one line: removing a single subproblem changes the growth rate of the whole algorithm. Big-number libraries still use Karatsuba for medium-sized inputs and switch to methods based on the fast Fourier transform for very large ones; Schoenhage-Strassen, for example, runs in O(n log n log log n).

§07

Problem set: 7 divide and conquer problems

Core + review

From fast power to multi-way merging, ending with a problem that mixes divide and conquer with binary search. Think for 30 seconds before opening a hint.

LC 169Majority ElementDivide and conquerBoyer-MooreReviewEASY

LC 50Pow(x, n)Fast powerRecursionDivide and conquerMEDIUM

LC 53Maximum SubarrayDivide and conquerDivide and conquer vs DPMEDIUM

LC 215Kth Largest Element in an ArrayQuickselectDecrease and conquerReviewMEDIUM

LC 148Sort ListMerge sortLinked listReviewMEDIUM

LC 23Merge k Sorted ListsMergeDivide and conquerLinked listHARD

LC 4Median of Two Sorted ArraysDivide and conquerBinary searchOptionalHARD

§08

Chapter quiz

✎ Quiz

Answer all 8 correctly to mark this chapter as complete.

QUESTION 01 / 8

What are the three steps of divide and conquer, in order?

QUESTION 02 / 8

Merge sort satisfies T(n) = 2T(n/2) + O(n). Using "work per level × number of levels", what is the running time?

QUESTION 03 / 8

Fast power computes x¹⁶ with how many squarings? (x² → x⁴ → x⁸ → x¹⁶ — count them.)

QUESTION 04 / 8

In the divide and conquer solution to Maximum Subarray (LC 53), why is the answer not simply max(best in left half, best in right half)?

QUESTION 05 / 8

You merge k sorted linked lists of length n each (N = kn nodes in total). What are the running times of "merge the others into the first list one at a time" and "merge in pairs"?

QUESTION 06 / 8

A classic fast power bug is computing x^(n/2) twice. Which line makes that mistake and falls back to O(n)?

QUESTION 07 / 8

Which of these are signals that a problem suits divide and conquer? (Select all that apply.)

QUESTION 08 / 8

Divide and conquer and dynamic programming both break a large problem into smaller ones. What is the real difference?

What to take away from this chapter

Divide and conquer is divide, conquer, combine: cut into smaller problems of the same form, solve each by recursion, then build the answer in the combine step. How hard a problem is usually depends on how expensive the combine step is.
You do not have to memorize the Master theorem. Draw the recursion tree and count work per level × number of levels. T(n)=2T(n/2)+O(n) → O(n log n); T(n)=T(n/2)+O(1) → O(log n). The theorem has gaps between its cases; the tree does not.
Fast power turns n multiplications into O(log n): x^n = (x^(n/2))², with one extra x when n is odd. The rule: compute x^(n/2) once. Writing it twice returns the time to O(n).
When merging k things, merge in pairs (log k rounds) instead of one at a time (k rounds): O(N log k) instead of O(k·N) (LC 23).
Know both solutions. LC 53: divide and conquer O(n log n) against Kadane O(n). LC 23: pairwise merging against a min-heap. The divide and conquer view often leads to segment trees; the DP or heap view is often faster.
Merging can count inversions at no extra cost: when a value is taken from the right half, add the number of values still waiting in the left half. A by-product of sorting answers a counting problem, still in O(n log n).
Always state the stack. Recursion depth is real memory: merge sort is O(n) auxiliary plus O(log n) stack, fast power is O(log n) stack (O(1) iterative), and LC 23 is O(log k) stack.
The line between divide and conquer and DP: independent, non-overlapping subproblems → divide and conquer (solve each once); overlapping subproblems → DP (store the results, or the same work is repeated, exactly as in the fast power computed twice).