—

Artificial Computational Intelligence

Divide and Conquer

Published: 2026-08-09

Level: postgraduate

Audience: Postgraduate students studying algorithm design techniques

We finished the greedy method in the last unit: we solved the fractional knapsack problem with a greedy algorithm, then worked through job sequencing with deadlines. There is still one greedy topic — interval partitioning — but we will come back to it later, because if job sequencing with deadlines is clear, interval partitioning is more or less the same idea. Today we start a new algorithm design strategy: divide and conquer, one of the best-known design techniques in all of algorithms.

This session works through the strategy itself, then three classic applications: merge sort, quick sort, and integer multiplication by divide and conquer. The thread that ties them together is the same three-step pattern — divide, recur, conquer — and the master theorem that prices it.

9.1 Divide and Conquer: The Strategy

9.1.1 The Three Steps: Divide, Recur, Conquer

What do you do when the problem in front of you is too big to solve in one shot — say, sorting a million records or searching a massive dataset? Most people, without any training, do the same thing: cut the problem into pieces and handle the pieces one at a time. Divide and conquer is that human instinct, turned into a precise algorithm design strategy.

Think of the strategy like cleaning a very messy house. You do not clean "the whole house" as one giant task; you divide it into rooms (divide), clean each room one at a time (recur), and at the end you check that every room is done so the whole house is clean (conquer). The analogy breaks in one place: cleaning a house room by room has no strict order, while divide and conquer always finishes every subproblem before combining, and the subproblems of a computer algorithm are independent pieces of the same problem, not different rooms with different rules.

Divide and conquer mirrors a human instinct. When a person faces a huge problem, the natural first move is to break it into parts and solve each part, if that is possible. That instinct is exactly what this strategy formalizes. It is a top-down technique: you look at the whole problem first, then cut it into pieces. Small instances are solved directly; large instances are always handled by this three-step recipe:

Divide — split the input data into two or more disjoint subsets; that is, divide the problem into smaller subproblems. We do this hoping that the solutions of the subproblems are easier to find. Nobody divides a problem without that hope — if the subproblems were as hard as the original, dividing would gain nothing. The subproblems should be smaller instances of the same problem, so the same strategy can be applied to them again.
Recur — solve the subproblems recursively: apply the same divide-and-conquer recipe to each piece, until the pieces become small enough to solve directly — that stopping point is covered in the next subsection.
Conquer (combine) — combine the partial solutions into the solution of the original problem. This step is easy to forget, but it is essential: after the subproblems are solved, you are not done until their solutions are merged back into one answer for the original problem. If the combine step is missing, you have solved a set of smaller problems but not the problem you started with.

Pitfall — skipping the conquer step. The divide step gets all the attention, but an algorithm that divides and solves the parts without combining them produces nothing. Conquer is where the answer to the original problem is assembled from the sub-answers. A common student mistake is to describe a divide-and-conquer algorithm with only "divide" and "recursively solve" — you must always state how the partial solutions are merged.

Takeaway: divide and conquer is a top-down strategy with three mandatory steps — divide into disjoint subproblems, recurse until the pieces are trivial, then combine the sub-solutions into the answer of the original problem. The combine step is the one most often forgotten.

Real-world: this three-step pattern appears all over computer science. Every recursive algorithm you have seen is an instance of it, and libraries that sort, search, and process huge datasets rely on it. Many problems are designed with this technique; we will work through the classic ones one by one — merge sort and quick sort for sorting, and integer multiplication for arithmetic.

9.1.2 Recursion, Recurrence, and the Master Theorem

Divide and conquer leans on recursion — the same function calling itself again and again. Each recursive call works on a smaller piece, and the calls keep going until the pieces hit the base case.

Q: Where did we first see recursion, and what came with it? A: In the algorithm analysis unit, under the topic of recurrence equations and the master theorem. The fundamental idea of the master theorem is exactly the structure of divide and conquer — which is why the theorem, and the recurrences behind it, return now as the analysis tool for every algorithm in this unit.

The general form of the recurrence to which the master theorem applies is

$T (n) = a T (\frac{n}{b}) + f (n)$

Every symbol has a job:

$T (n)$ (read "T of n") is the running time of an algorithm on a problem of size $n$ .
$a$ is the number of subproblems the problem is split into. In divide and conquer, $a$ is two or more.
$b$ tells us the size of each subproblem: each subproblem has size $n / b$ . The sizes need not all be the same — if we split into two, the subproblems could be size $n /2$ , $n /3$ , and so on.
$f (n)$ attributes the time taken to divide the problem as well as the time taken to combine the solutions of the subproblems after they are solved recursively.

The professor insists you read this recurrence in English rather than staring at symbols: a problem of size n is divided into a subproblems of size n/b, and f(n) is the time taken for dividing the problem and combining the solution.

That last point is the one that ties the master theorem to divide and conquer: the recurrence's $f (n)$ term is exactly the divide step plus the conquer (combine) step. If you do not read the master theorem this way — a problem of size $n$ split into $a$ subproblems of size $n / b$ , with $f (n)$ the cost of dividing and combining — the theorem stays an empty formula. Read it in English first, and the cases will make sense.

Scope — when the recurrence applies. The master theorem applies to recurrences of exactly this shape: $a \geq 1$ subproblems, each of size $n / b$ with $b > 1$ , and a base case $T (1) = Θ (1)$ (a constant-size problem solved in constant time). It does not directly handle unequal splits such as $T (n) = T (2 n /3) + T (n /3) + Θ (n)$ , and it cannot be applied when $f (n)$ is not "comparable" to $n^{l o g_{b} a}$ (the gap between the cases). For this course the essential habit is the English reading — the cases themselves are applications of that reading.

Visual intuition — the recursion tree. Picture the recurrence as a tree. The root represents the original problem of size $n$ and carries cost $f (n)$ . Below it, $a$ children represent the subproblems of size $n / b$ , each carrying cost $f (n / b)$ . Below those, $a^{2}$ grandchildren of size $n / b^{2}$ , each with cost $f (n / b^{2})$ , and so on. The tree has height $lo g_{b} n$ (the number of times $n$ must be divided by $b$ before it becomes 1) and $n^{l o g_{b} a}$ leaves, each a constant-size base case costing $Θ (1)$ . The total running time is the sum of all node costs down the tree. For merge sort, this tree will give the whole analysis — every level costs $Θ (n)$ , and there are $lo g_{2} n$ levels.

9.1.3 Base Cases

Every recursion needs a base case, and the definition matters more than it looks.

Q: What is the base case of a recursion? A: It is the case that needs no recursive call to solve — you can solve it directly in constant time. Saying "the base case is where the algorithm ends" is true but weaker; the meaningful part is that no further recursive call is needed. So the base cases of a divide-and-conquer recursion are the subproblems of constant size — for merge sort, a one-element array, which is already sorted.

The advantage of a constant-size base case is that no more procedures are called for it: it is solved outright. Everything above it in the recursion tree is handled by recursive calls; the base case is where the calls stop.

Pitfall — "the base case is where the algorithm ends." The professor called this out explicitly: ending is a consequence, not the definition. The definition is structural — a base case is a subproblem small enough that it can be solved directly, with no recursive call. Confusing the two makes it easy to design recursions that never bottom out (no base case) or that bottom out too late (huge base cases that cost too much to solve directly).

Pitfall — too-large base cases. A base case must be constant size so that it is solved in constant time. If you stop the recursion at size $n /2$ and solve that directly, the "direct" solution is no longer constant-time, and the running-time analysis breaks down.

Analysis note: the running time of divide-and-conquer algorithms is analyzed with recurrence equations or with the master theorem — either tool works; we will use both on merge sort shortly.

Exam note: The master theorem is assumed known from the earlier unit on recurrence equations — it will not be re-explained in the exam, and the expected answer style is the English reading: a problem of size n is divided into a subproblems of size n/b, and f(n) is the divide-and-combine time. The base case is examinable in its precise form: the case that needs no recursive call and is solved directly in constant time.

9.1.4 The Three Cases of the Master Theorem

For the recurrences in this unit we need the three cases of the master theorem, stated in terms of the comparison between $f (n)$ and $n^{l o g_{b} a}$ — the "critical exponent" fixed by $a$ and $b$ :

Case 1 — leaves dominate: if $f (n) = O (n^{l o g_{b} a - ε})$ for some constant $ε > 0$ , then $T (n) = Θ (n^{l o g_{b} a})$ . The cost is concentrated in the constant-size leaves of the recursion tree.
Case 2 — every level costs the same: if $f (n) = Θ (n^{l o g_{b} a})$ , then $T (n) = Θ (n^{l o g_{b} a} lo g n)$ . Each level of the tree carries the same total cost, so the total is the per-level cost times the height.
Case 3 — root dominates: if $f (n) = Ω (n^{l o g_{b} a + ε})$ for some constant $ε > 0$ and the regularity condition $a f (n / b) \leq c f (n)$ holds for some constant $c < 1$ , then $T (n) = Θ (f (n))$ . The divide-and-combine cost at the top outweighs everything below.

The intuition is a race between two quantities: the work done at the root and upper levels ( $f (n)$ and its descendants) versus the work done at the leaves ( $n^{l o g_{b} a}$ base cases). Whoever dominates the recursion tree determines the answer. When the two are exactly equal (case 2), the answer picks up an extra $lo g n$ factor — the tree height.

A first example, which we will use as the merge sort recurrence shortly: $T (n) = 2 T (n /2) + Θ (n)$ . Here $a = 2$ , $b = 2$ , so $n^{l o g_{b} a} = n^{l o g_{2} 2} = n$ . Since $f (n) = Θ (n) = Θ (n^{l o g_{b} a})$ , case 2 applies and $T (n) = Θ (n lo g n)$ . Keep this picture in mind: the professor returns to this exact recurrence when analyzing merge sort.

Recap and bridge: divide and conquer formalizes the everyday instinct of breaking a huge problem into parts — divide, recurse, conquer — and its cost is captured by the recurrence $T (n) = a T (n / b) + f (n)$ , read in English as "a subproblems of size n/b, with f(n) the divide-and-combine time." The three master-theorem cases then decide how fast the algorithm is. Next we see the first real algorithm built on this spine: merge sort, whose divide-and-conquer structure is simple enough to watch working end to end.

9.2 Merge Sort

Merge sort is the first algorithm we study under divide and conquer. The concept is the same three-step pattern: divide, recur, conquer. We divide the problem of sorting $n$ elements into two subproblems of sorting $n /2$ elements each. We recursively sort those two subproblems — call them $s_{1}$ and $s_{2}$ — which means each of them is again divided into two subproblems of size $n /4$ (sub-subproblems $s_{11}, s_{12}, s_{21}, s_{22}$ ), and so on. Then we conquer: we merge the sorted solutions of $s_{1}$ and $s_{2}$ into a unique sorted sequence.

Q: Is recursion designed based on divide and conquer? A: The other way around: divide and conquer is based on recursion. The strategy is implemented through recursive calls on the subproblems — each subproblem is solved by calling the same sorting procedure on a smaller range, until the ranges hit the base case.

9.2.1 The Algorithm

How would you merge two sorted piles into one? You look at the top card of each pile and take the smaller one, again and again. That is exactly the merge step of merge sort — and the reason the combine step costs so little is that both piles are already sorted. The whole algorithm is just: split in half, sort each half recursively, then run this two-pile merge.

Let $L$ be the lowest index of the array (the left end) and $R$ the highest index (the right end). The first step of the algorithm is to find the middle point:

$m = \frac{L + R}{2}$

Here $m$ is the middle index (integer division), the division point of the array. For the example we will trace, indices run from 0 to 6, so $m = (0 + 6) /2 = 3$ , and the array is divided at index 3.

Each call to merge sort does exactly three things, and because the calls are recursive, every call runs all of them:

Find the middle, $m = (L + R) /2$ — the division point.
Call merge sort on the first half, the array from $L$ to $m$ — the left subproblem.
Call merge sort on the second half, the array from $m + 1$ to $R$ — the right subproblem.
Call merge, the combine step that merges the two sorted halves into one sorted sequence.

Scope — the middle index with an odd-sized array. The professor's example has indices 0–6, so $(0 + 6) /2 = 3$ is exact. When the highest index is odd — say indices 0 to 7, so $(0 + 7) /2 = 3.5$ — you may take index 3 or index 4. Whether one subarray ends up with one extra element makes no difference to the time complexity: both halves are still of size $n /2$ up to rounding, and the analysis goes through unchanged.

The recursion stops when the range has one element (or none): a single element is already sorted, so no recursive call is needed — that is the base case. Everything above the base case is handled by the four steps.

9.2.2 Worked Example: Sorting [38, 27, 43, 3, 9, 82, 10]

We sort the array $[38, 27, 43, 3, 9, 82, 10]$ , indices 0–6.

Level 1 divide: $m = (0 + 6) /2 = 3$ , so the array splits into:

left subarray: $[38, 27, 43, 3]$ (indices 0–3)
right subarray: $[9, 82, 10]$ (indices 4–6)

Left half, $[38, 27, 43, 3]$ , indices 0–3: $m = (0 + 3) /2 = 1$ , so it splits into $[38, 27]$ and $[43, 3]$ .

$[38, 27]$ is a base case (two elements). Merge: compare 38 and 27 — 27 is smaller, so 27 is copied to the output first, then 38. Result: $[27, 38]$ .
$[43, 3]$ is a base case. Merge: compare 43 and 3 — 3 is smaller, copied first, then 43. Result: $[3, 43]$ .
Merge the two sorted results $[27, 38]$ and $[3, 43]$ : compare 27 with 3 — 3 is smaller, so 3 is copied from the right subarray, and the pointer in the right subarray advances to 43. Compare 27 with 43 — 27 is copied from the left subarray, pointer advances to 38. Compare 38 with 43 — 38 is copied, left subarray is over. Whatever remains in the right subarray is copied as-is: 43. Result: $[3, 27, 38, 43]$ .

Right half, $[9, 82, 10]$ , indices 4–6: $m = (4 + 6) /2 = 5$ , so it splits into $[9, 82]$ and $[10]$ .

$[9, 82]$ is a base case. Merge: compare 9 and 82 — 9 is smaller, copied first, then 82. Result: $[9, 82]$ .
$[10]$ is a single element, already sorted.
Merge $[9, 82]$ with $[10]$ : compare 9 with 10 — 9 is copied from the left subarray, pointer advances to 82. Compare 82 with 10 — 10 is smaller, copied; the right subarray is over. Whatever remains in the left subarray is copied as-is: 82. Result: $[9, 10, 82]$ .

Final merge: merge $[3, 27, 38, 43]$ with $[9, 10, 82]$ , element by element:

Compare 3 and 9 — 3 is smaller, copied; pointer advances in the left subarray to 27.
Compare 27 and 9 — 9 is smaller, copied; pointer advances in the right subarray to 10.
Compare 27 and 10 — 10 is smaller, copied; pointer advances in the right subarray to 82.
Compare 27 and 82 — 27 is smaller, copied; pointer advances in the left subarray to 38.
Compare 38 and 82 — 38 is smaller, copied; pointer advances to 43.
Compare 43 and 82 — 43 is copied; the left subarray is over.
Copy whatever remains in the right subarray as-is: 82.

Final sorted array: $[3, 9, 10, 27, 38, 43, 82]$ .

Sense-check: the output has all seven elements of the input, in ascending order — 3 is the smallest of the seven, 82 the largest, and each next element is bigger than the previous.

Notice the pattern in every merge: the two subarrays are each already sorted, so at every step we compare the two front elements and copy the smaller one; the pointer advances only in the subarray where the copying happened.

Q: In the merge of [27, 38] with [3, 43], will 38 also be compared with 3? A: No — and that is the catch of the merge step. Whenever we start combining, the left and right subarrays are each already sorted by themselves. An element is compared only when the pointer reaches the front of its own subarray; there is no need to re-compare an element that was already copied. In the example: 27 vs 3 → 3 copied; 27 vs 43 → 27 copied; 38 vs 43 → 38 copied; only 43 is left, copied as-is.

The same reasoning answers the natural follow-up doubt:

Q: What about the left-out items in an array — don't they get compared? A: If one subarray finishes first, whatever remains in the other subarray is simply copied in the same order it already appears, because those remaining elements are already sorted. There may be several elements left, not just one — they are all copied as-is.

9.2.3 The Merge Step and a Second Example

The conquer step of merge sort consists of merging two sorted sequences: we combine two sorted sequences $a$ and $b$ into one larger sorted sequence containing the union of their elements. We do not compare every element of one subarray with every element of the other; we only compare the two front elements at each step, because both input sequences are sorted. This is the doubt that was raised in class, and it is the reason the merge runs in linear time.

The merge step takes $Θ (n)$ time: the two subarrays together hold $n$ elements, and we go through each element at least once. Merging two sorted sequences of $n /2$ elements each takes $n$ time — merging two 2-element subarrays takes 2 steps' worth of work, merging two 4-element subarrays takes 4, always the total number of elements involved.

A second worked merge: left subarray $[3, 10, 25, 54]$ , right subarray $[1, 5, 23, 75]$ .

Compare 3 and 1 — 1 is smaller, copied; right pointer advances to 5.
Compare 3 and 5 — 3 is smaller, copied; left pointer advances to 10.
Compare 10 and 5 — 5 is smaller, copied; right pointer advances to 23.
Compare 10 and 23 — 10 is smaller, copied; left pointer advances to 25.
Compare 25 and 23 — 23 is smaller, copied; right pointer advances to 75.
Compare 25 and 75 — 25 is smaller, copied; left pointer advances to 54.
Compare 54 and 75 — 54 is smaller, copied; the left subarray is completely over.
Copy the remaining elements of the right subarray as-is: 75.

Merged result: $[1, 3, 5, 10, 23, 25, 54, 75]$ .

Sense-check: eight comparisons copied every element exactly once — the total work is the total number of elements, $n = 8$ , which is exactly the $Θ (n)$ merge cost.

The merge step is $Θ (n)$ because we go through each element of both subarrays at least once — $n /2$ elements here and $n /2$ there, so $n$ work in total. You can implement the merge with a doubly linked list or with an array; that choice is up to you — what changes is the memory layout, not the comparison logic.

9.2.4 Order of Execution (Depth-First)

The slides show the whole process at once, but the steps do not all happen in parallel. Every call to merge sort runs: find the middle, merge sort the first half, merge sort the second half, then merge. Because the first half is processed before the second half, the entire left-hand side of the recursion tree — all of the leftmost subarrays — is completely divided and merged before the right half of the array is even started.

So the order of execution is:

The main array is divided into its two halves.
The left half is divided again, and again, down to the leftmost base case.
The leftmost merge happens (38 and 27, then 43 and 3 in our example).
The left side combines upward — the leftmost pair merges, then the next, then those two results merge — and only when all left-side processing is complete does the right half of the array begin.
The same divide-merge process runs on the right half.
The two sorted halves are merged at the end.

Concretely, in the example: [38, 27] is merged first, then [43, 3], then those two results merge to [3, 27, 38, 43]; only then does the right half [9, 82, 10] start dividing and merging; finally the two big sorted halves merge.

Q: Does "order of execution" mean which index, left or right, is used next? A: No — it means what happens first, second, third, and so on. The whole process is not simultaneous: the leftmost subarrays all finish before the next subarray starts, because the calls are recursive. The best way to see this is to implement merge sort in any language and number the recursive calls (or trace the program). Explaining it any number of times will not make it as clear as watching it once.

Exam note: expect a question on the order of execution in the final exam — either "give the order of execution" or "which step does this particular sequence arrive at in merge sort." You must be able to say, for a given intermediate sequence, exactly which merge produced it and in what order the merges happen.

Warning — trace it yourself. The professor's explicit advice: implement merge sort, number the recursive calls, and watch the order of execution. The output may surprise you — the sequence that appears in the middle of the run is often not what you expect from looking at the final picture. This is compulsory practice, even though it will not be done in class.

9.2.5 Complexity Analysis: O(n log n)

The analysis of merge sort is the same recursion-tree picture from the earlier unit, so keep that derivation handy. We have a problem of size $n$ , divided into two subproblems of size $n /2$ ; each of those divides into two subproblems of size $n /2$ , which makes size $n /4$ , and so on.

The work done at each level is $Θ (n)$ . Whether we are dividing or merging, at the end of the day we process each element at least once — the number of elements is not reducing, only the size of the pieces: $n /2 + n /2 = n$ , then $4 \times (n /4) = n$ , and so on. Each level costs $n$ , so the total is the level cost times the number of levels.

The height of the tree is $lo g_{2} n$ , because we divide the problems into two parts at every level. So the total work is

$n \cdot lo g_{2} n$

and the time complexity of merge sort is $O (n lo g n)$ .

Visual intuition — the recursion tree. Draw the tree with the original array at the root: level 0 has 1 node holding $n$ elements, level 1 has 2 nodes holding $n /2$ each, level 2 has 4 nodes holding $n /4$ each, and so on down to $n$ leaves holding 1 element each at level $lo g_{2} n$ . The merge cost at each node is proportional to its size, so each complete level sums to $n$ total work. The total cost is the rectangle: level cost $n$ times height $lo g_{2} n$ — the picture is a rectangle of area $n lo g_{2} n$ , which is exactly the formula above.

The same result follows from the master method. The recurrence is $T (n) = a T (n / b) + f (n)$ with $a = 2$ and $b = 2$ , and $f (n)$ is the time to divide the problem and combine the solutions — here that is constant-time division plus the linear merge, so $f (n) = Θ (n)$ . The critical exponent is $n^{l o g_{2} 2} = n$ , so $f (n)$ and $n^{l o g_{b} a}$ match exactly: case 2 of the master theorem applies, and the solution is $n lo g n$ . The recurrence reads in English exactly as before: a problem of size $n$ is divided into two subproblems of size $n /2$ , and the divide-and-combine cost is $f (n)$ .

Scope — the assumptions behind $O (n lo g n)$ . The clean derivation assumes the array splits into two halves of equal size (conveniently true when $n$ is a power of 2; otherwise the halves differ by one element, which changes nothing asymptotically). It also assumes the base case is constant size. If a different base-case size were chosen, the $Θ (n lo g n)$ order of growth would not change — only the hidden constant. What would break the analysis is an unbalanced split (like a 1-to- $n - 1$ split), which is precisely the trap quick sort can fall into, as we will see.

9.2.6 Properties: Non-Adaptive, Stable, Not Incremental, Not Online, Not In Place

These properties matter in practice, and the professor included them deliberately — they are programming concepts you are expected to know.

Non-adaptive. An adaptive sorting algorithm is one whose running time changes with the order of elements in the input: an already-sorted array takes less time, a descending array takes more. Some sorting algorithms depend on the input order. Merge sort is not one of them. Irrespective of the order of elements, we follow the same process — divide, recurse, merge — and the time is always $n lo g n$ . So merge sort is a non-adaptive algorithm: its worst case and its best case cost the same.

Stable or unstable. This word needs its sorting-specific meaning, and the professor corrected the everyday reading of it:

Q: When do we say a sorting algorithm is stable? (Answers offered: it finishes in finite time, it gives the same output every time, it behaves fine in implementation.) A: Those answers come from the English meaning of the word "stable." In sorting, "stable" has a precise meaning: two objects with equal keys appear in the same order in the sorted output as they appear in the input array. A sorting algorithm is stable if equal-key items keep their input order in the output — such an algorithm is called a stable algorithm.

The classroom example was sorting invented names by last name after they were already sorted by first name. Input order: Carol, Dave, Ken (then Alex, Bob — the first-name sort). Several people share the same last name — say Carol, Dave, and Ken all have the same last name.

A stable algorithm keeps them in the order they appeared in the input array: Carol, Dave, Ken.
An unstable algorithm may place them in any order — Ken before Carol, for instance — while the output is still correctly sorted by last name.

A second illustration used ordered pairs sorted by their first component: in the input array, the pair $(9, 8)$ appears before $(9, 7)$ . A stable sort outputs $(9, 8)$ first and $(9, 7)$ second, because $(9, 8)$ appears first in the input; an unstable sort may place $(9, 7)$ first — still sorted by the first component, but with the equal-key pair in a different order.

Takeaway: stability is about equal keys only — it says nothing about how unequal keys are arranged; they are ordered by the key either way.

Q: Between a stable and an unstable output, which is correct? A: Both are correct — both outputs are sorted by the key. Stability is a preference, not a correctness property: if you want the input order of equal-key items preserved in the output, use a stable sort; if you do not mind, any sorting algorithm will do.

The single sign that decides stability. The same algorithm can be coded as a stable or an unstable sort. When you merge, if the left and right elements are equal, copying from the left subarray preserves their input order. A single sign change makes the difference — using $\leq$ instead of $<$ when comparing. Think through what you want to happen when the elements being compared are equal, and you will see why the comparison operator decides stability. The algorithm concept itself does not change; the choice is an implementation detail.

Not incremental. An incremental algorithm sorts elements one by one as they arrive. Merge sort is not incremental: it needs all the elements before it starts sorting, because only then can it divide. It cannot sort elements as they come in.

Not online. Online algorithms process the input piece by piece in a serial fashion: bring a few elements into main memory, sort them, bring the next few, sort again. Merge sort is not online — we need the complete array in main memory before we can start. Insertion sort, by contrast, is online: you can bring half the elements to memory, sort them, then bring the rest and continue sorting. (The professor's first phrasing had it backwards and was corrected on the spot: insertion sort is online, merge sort is not.) This matters for streaming applications: if the data arrive continuously, an online algorithm such as insertion sort can start immediately, while merge sort must wait for the whole input.

Not in place. An in-place algorithm transforms the input using no auxiliary data structure: it may use auxiliary variables, but it does not need a completely separate data structure. The input array is rearranged — the input is usually overwritten by the output. Merge sort is not in place, because the merge step needs an output array. The professor worked through the reason:

Why standard merge sort is not in place — the counterexample. Suppose the left subarray is $[3, 4, 5]$ and the right subarray is $[1, 2]$ . Conceptually we divided one array into left and right, but in the implementation it is the same array undergoing the process. In-place, 1 would replace 3 and 2 would replace 4 — and then 3 and 4 are gone. Where did they go? Lost. That is the reason the standard merge sort is not in place: writing the merged elements into the first positions overwrites left-subarray elements that have not been copied yet. The merge writes 1 into position 0 and 2 into position 1 while 3 and 4 still sit unread in positions 0 and 1 — the writing destroys elements the algorithm still needs.

If you can think of a workaround that writes 1 and 2 into the first two positions without losing 3 and 4, you can make merge sort in place — but the standard algorithm is not.

Q: Does the implementation actually create all these subarrays in memory? A: No. The division into left and right subarrays is conceptual, for our understanding. In the implementation, nothing is physically split into separate storage locations; the work happens as rearrangements of array indices — elements get compared, exchanged, and copied within the same array. It is exactly like the binary tree picture of a BST: the tree representation is in our mind, not in memory. Implement it in a programming language and watch how the execution actually happens.

Recap — stability and implementation again. A sorting algorithm is stable if two objects with equal keys appear in the same order in the sorted output as in the input array. All these array-sorting algorithms can be made stable or unstable depending on how you implement the comparison. For merge sort, the equal case is the decision point: when the left element equals the right element, choose which one to copy first — copying from the left subarray keeps the algorithm stable.

9.2.7 Applications of Merge Sort

Real-world: merge sort is often the best choice for sorting a linked list. In a linked list, random access is difficult — to reach the $i$ -th node you must traverse from the head one node at a time. Merge sort rarely needs random access: it works by finding the middle, dividing, and merging sequentially, the same way linked lists are traversed. So merge sort sorts linked lists very efficiently.

Real-world: external sorting — a class of sorting algorithms that handle massive amounts of data that do not fit into the main memory of the computing device; the data reside on slow external memory such as a hard disk drive. The standard approach is an external merge sort using a hybrid sort-merge strategy. In the sorting phase, chunks of data small enough to fit in main memory are read, sorted, and written out to temporary files. In the merge phase, the sorted subfiles are combined into larger files. Instead of bringing the complete data into main memory — which may not be possible — you read part, sort it, store it temporarily, bring the next chunk, and finally combine the files into a larger sorted file. These are modifications of the standard merge sort; you add the extra logic to get it done.

Real-world: the Java Arrays.sort method uses merge sort. Real-world: the Linux kernel uses merge sort for linked lists, because merge sort is the best option there. Real-world: Python has an algorithm called Timsort, which is a combination of merge sort and insertion sort — worth searching and reading about. There is also a step-by-step execution example available to walk through at home; the honest way to use it is to implement merge sort, run it, and check your trace against the example.

Domain connection: merge sort is the workhorse of systems that must sort without random access (linked lists in the Linux kernel), without fitting the data in memory (external sorting of database-sized files), and without losing the input order of equal keys (Timsort's stable merge in Python). The reason one algorithm serves all these settings is that its structure — sequential divides and merges — matches the way such systems actually move data.

9.2.8 Remaining Questions and Answers

Q: Every time a problem is divided into subproblems, do both subproblems start at index zero? A: Yes, for conceptual understanding. When the division actually happens, the recursion works on ranges of indices of the same array — the first half and the second half are index ranges, not new arrays starting at zero.

That is the same point as the "no subarrays in memory" question above: the pictures of separate arrays are a mental aid; the code passes index ranges.

Q: Can you explain the master method once more? A: Not now — it took about half a session to explain the first time. Go back to the earlier material on recurrence equations and the master theorem; for this course, the essential habit is reading the recurrence in English: a problem of size n splits into a subproblems of size n/b, with f(n) the cost of dividing and combining.

Q: Do we get questions from this topic in the exam? A: Yes, you will. If I ask anything, it will be about the order of execution — give the order of execution, or say which step in merge sort a particular sequence arrives at. So implement merge sort, number the recursive calls, and trace it. You might be shocked: the output you get may not be what you expect. This is compulsory practice, even though it will not be done in class.

Recap and bridge: merge sort splits the array in half, sorts each half recursively, and merges the two sorted halves in linear time — giving a rock-solid $O (n lo g n)$ on every input, at the cost of needing an output array for the merge and the whole input in memory. Next we meet its famous cousin, quick sort, which does the divide step the clever way — but pays for it with a worst case that is far from $n lo g n$ .

9.3 Quick Sort

Quick sort was assigned as self-reading, but one example is worked in class. Listen carefully: there are many slightly different versions of quick sort online — any concept, any program you like is fine, because the concept remains the same. Understand one logic thoroughly and do not let the other variants confuse you.

9.3.1 The Partition Scheme (Pivot, i, j)

Merge sort made the combine step do the heavy lifting and kept the divide trivial (split in half). What if we flip that: make the divide step smart — place one element exactly where it belongs in the final sorted array — so that the combine step becomes completely free? That is the idea of quick sort: the pivot does the sorting work during the division, and the conquer step is nothing at all.

Quick sort has a pivot element — an element chosen to be placed at its correct sorted position. We use two pointers $i$ and $j$ , plus the concept of partitioning the array around the pivot. In the version shown in class:

We work on the array between low and high (array indices). First we check whether low ≤ high; this ensures there are elements in the array.
The pointer $i$ is set to low + 1, the element right after the pivot position.
The pointer $j$ is set to high, the last index.
The pivot is the first element of the array, A[low]. (Other implementations make the pivot the last element or the median — all valid variations; settle on one logic and understand it fully first.)

Then three checks are repeated, in this order:

Is pivot > $A [i]$ ? If yes, increment $i$ and repeat. This check walks $i$ rightward past elements smaller than the pivot, because smaller elements belong on the left of the pivot.
Otherwise, is $A [j]$ > pivot? If yes, decrement $j$ and repeat. This check walks $j$ leftward past elements larger than the pivot, because larger elements belong on the right of the pivot.
Otherwise (both comparisons are no), is $i \leq j$ ? If yes, exchange $A [i]$ and $A [j]$ , and repeat from check 1. If no — $i$ has crossed beyond $j$ — exchange $A [j]$ with the pivot, and the partition is done.

Formally, the three comparisons are:

$pivot > A [i], A [j] > pivot, i \leq j$

The whole intention is to get the pivot to its correct position: after one partition, every element to the left of the pivot is smaller than the pivot and every element to the right is larger. Then we repeat the same process on the left subarray and on the right subarray — divide and conquer again, but now with a combine step that costs nothing: once the left and right subarrays are sorted, the whole array is sorted, because every element of the left side is already smaller than every element of the right side.

Scope — what the three checks assume. The scheme assumes the pivot sits at A[low] and that i starts just after it; the version where the pivot is the last element or the median uses different pointer logic. All versions produce the same guarantee — after one partition the pivot is at its final sorted position — but the exact order of the checks is tied to the pivot position. On the exam, state your pivot choice and apply its scheme consistently; mixing schemes is how trace errors creep in.

9.3.2 Worked Example: Partitioning [44, 75, 23, 43, 55, 12, 64, 77, 33]

Array: $[44, 75, 23, 43, 55, 12, 64, 77, 33]$ , indices 0–8. low = 0, high = 8, pivot = 44, $i = 1$ , $j = 8$ .

Round 1. Is pivot > $A [1] = 75$ ? No. Is $A [8] = 33$ > pivot (44)? No. Is $i \leq j$ (1 ≤ 8)? Yes — exchange $A [1]$ and $A [8]$ : 75 and 33 swap.

Array: $[44, 33, 23, 43, 55, 12, 64, 77, 75]$ .

Round 2. Repeat: pivot > $A [1] = 33$ ? Yes, increment $i$ → 2. Pivot > $A [2] = 23$ ? Yes, increment $i$ → 3. Pivot > $A [3] = 43$ ? Yes, increment $i$ → 4. Pivot > $A [4] = 55$ ? No.

Is $A [j] = A [8] = 75$ > pivot? Yes, decrement $j$ → 7. Is $A [7] = 77$ > 44? Yes, decrement $j$ → 6. Is $A [6] = 64$ > 44? Yes, decrement $j$ → 5. Is $A [5] = 12$ > 44? No.

Is $i \leq j$ (4 ≤ 5)? Yes — exchange $A [4]$ and $A [5]$ : 55 and 12 swap.

Array: $[44, 33, 23, 43, 12, 55, 64, 77, 75]$ .

Round 3. Repeat: pivot > $A [4] = 12$ ? Yes, increment $i$ → 5. Pivot > $A [5] = 55$ ? No.

Is $A [j] = A [5] = 55$ > 44? Yes, decrement $j$ → 4. Is $A [4] = 12$ > 44? No.

Is $i \leq j$ (5 ≤ 4)? No — $i$ has crossed $j$ , so we do not exchange $A [i]$ and $A [j]$ . Instead, exchange $A [j] = A [4] = 12$ with the pivot 44.

Array: $[12, 33, 23, 43, 44, 55, 64, 77, 75]$ .

Sense-check: the pivot 44 sits at index 4, with every element to its left (12, 33, 23, 43) smaller than 44 and every element to its right (55, 64, 77, 75) larger — so 44 is now in its final sorted position, exactly as the three checks promised.

That is one iteration of quick sort. After the first iteration the pivot 44 is in its correct sorted position (index 4): every element to its left is smaller than 44, every element to its right is larger. The pivot is sorted. Now repeat the process on the left subarray $[12, 33, 23, 43]$ and the right subarray $[55, 64, 77, 75]$ — for example with 12 as the new pivot on the left and 55 as the new pivot on the right. No merge is needed afterward: the subarrays are disjoint, and everything on the left is already smaller than everything on the right.

Visual intuition — one partition at a time. Picture the array as a row of boxes with the pivot marked at the left. The two pointers $i$ (from the left) and $j$ (from the right) sweep toward each other; boxes with values smaller than the pivot are skipped by $i$ , boxes with values larger are skipped by $j$ , and whenever both pointers are stuck on misplaced values they swap. When the pointers cross, the pivot is dropped into the gap — the boxes left of the gap are all smaller, right of the gap all larger. One iteration produces a single sorted element (the pivot); the two sides are then solved independently, and the final array is sorted with no combine step at all.

The mechanical early steps make sense only in hindsight: check 1 pushes $i$ past elements smaller than the pivot, check 2 pushes $j$ past elements larger than the pivot, the index comparison decides which elements to exchange, and the final exchange seats the pivot at its correct position.

9.3.3 Complexity and the Worst Case

The time complexity of quick sort on the average case is $O (n lo g n)$ , same as merge sort. The analysis is left to the recorded material and self-reading. The worst case deserves conceptual understanding.

Q: When does the worst case of quick sort happen? (Common answers: when the array is already sorted, or in descending order.) A: Those are close but not the correct answers — I will not accept "sorted or descending array" as the answer. The worst case happens when the pivot is the smallest or the largest element in the subarray. Suppose you pick the smallest element, 12, as pivot: after the first iteration, 12 lands in its sorted position at the very front, and all the remaining $n - 1$ elements are still unsorted in one big subarray. You are not able to exploit divide and conquer — you gained one element instead of dividing the problem in half. The same thing happens when the pivot is the largest: it lands at the very end, leaving the whole rest of the array as one subproblem. That is when the time complexity goes to $O (n^{2})$ .

The distinction matters: an already sorted array is not automatically the worst case, because you can still manage by choosing a smart pivot. The fundamental problem is an extreme pivot — smallest or largest — not the input order. With an extreme pivot, the pivot will not move toward the middle; it stays at the first or last position, and the remaining whole array is still there, equivalent to $n$ , with only one element's benefit — not the $n /2$ benefit divide and conquer needs.

Why the extreme pivot costs $O (n^{2})$ . Each partition of an $n$ -element subarray costs $Θ (n)$ (every element is inspected once by the pointers). If every partition removes only the pivot, the recursion is $T (n) = T (n - 1) + Θ (n)$ — the subproblem shrinks by one element each time, not by half. Unrolling: $Θ (n) + Θ (n - 1) + \dots + Θ (1) = Θ (n^{2})$ , the sum of an arithmetic series. The recursion tree is not a balanced tree of height $lo g_{2} n$ , but a single chain of height $n$ . Compare that with a balanced split: $T (n) = 2 T (n /2) + Θ (n)$ gives $Θ (n lo g n)$ — the exact merge-sort picture. The whole game of quick sort is keeping the split from being extreme.

The normal tendency is to choose the median of the array as the pivot, and you understand why: if you choose the median, you are guaranteed to get a left subarray and a right subarray, a balanced split.

Q: In the exam, which pivot should I choose? A: Your choice — the first element, the median, or the last element; just make your choice. In the exam you can pick the first or last element without much damage, under the assumption that the elements are not all skewed; the median guarantees balance.

Pitfall — saying "sorted input" is the worst case. The professor was explicit: this answer will not be accepted. Sorted (or descending) input often pairs with an extreme pivot — when the pivot is the first element and the input is sorted, the pivot is the smallest or largest — but the cause is the pivot's position, not the input's order. Ask "is the pivot the smallest or the largest element of the subarray?" — if yes, the split is 1 to $n - 1$ and the cost becomes quadratic, no matter how the input was arranged.

Pitfall — hoping for balance without choosing it. Quick sort is only $O (n lo g n)$ when every partition leaves two nonempty sides of roughly comparable size. Relying on "the average case will be fine" is reasonable for random data, but a sorted or nearly sorted array with a fixed first-element pivot will reliably produce the extreme split. The median pivot — or a random pivot — removes that dependence.

9.3.4 Study Expectations and Notes

A few words from the professor about learning style, because they shape how you should study quick sort: do not be adamant about learning only what is taught in class. There is a lot of research and literature on this topic; PG students are expected to read around the material. The basic thread is given in the contact sessions, but these are emerging areas with research happening around them, so read through whenever you get time. Theory and getting marks are two different things: programming is out of the scope of the class, but conceptual understanding is what is being covered — implementation you must do yourself. There is a good textbook reference — the Goodrich Python implementation — and opening it once or twice builds much more confidence. Working professionals have real time constraints, and everyone understands that; the course demands a lot more effort from your end because of that.

Exam note: the worst case of quick sort is the exam point: it happens when the pivot is the smallest or the largest element in the subarray, giving $O (n^{2})$ — not merely when the input is sorted or descending. In the exam you choose the pivot yourself — first element, median, or last element — and the median is the choice that guarantees a left and a right subarray.

Recap and bridge: quick sort wins its speed from the divide step — a pivot is seated at its final position with three comparisons and two pointers, so the combine step disappears entirely; the price is a worst case of $O (n^{2})$ whenever the pivot is an extreme element. Where merge sort and quick sort both reach $O (n lo g n)$ on average, the divide-and-conquer idea now appears even in arithmetic: next, multiplying huge integers by splitting the numbers themselves.

9.4 Integer Multiplication by Divide and Conquer

Integer multiplication is the last topic of the session — we will lay the foundation now, because it is very important, and the concept must be crystal clear before the next session.

9.4.1 Why Big-Integer Multiplication Matters

How do you multiply two numbers too large to fit in a processor's registers — numbers with thousands of bits? The schoolbook method you learned in primary school costs $O (n^{2})$ digit operations, and for the numbers used in modern cryptography that is far too slow. This section shows how divide and conquer cuts the cost — and why the trick boils down to the price of multiplying by powers of the base.

We are dealing with the problem of multiplying big integers: numbers so large that they cannot be handled directly by the arithmetic logic unit (ALU) of a single processor. Given two big integers $I$ and $J$ , each represented with $n$ bits, we can easily compute $I + J$ or $I - J$ — everyone knows how, and each takes $Θ (n)$ time, where $n$ is the number of bits. But multiplication is different: the product of two binary (or decimal) numbers by the normal, elementary-school algorithm takes $O (n^{2})$ time. When $n$ is huge — and that is exactly the situation we care about — $n^{2}$ is really, really costly. We cannot afford an $n^{2}$ algorithm. So we use divide and conquer to multiply two large integers faster.

Q: Where do we actually need big-integer multiplication? A: Astronomy and quantum theory were suggested as fields with huge numbers. The cleanest computer science example is cryptography: in the RSA algorithm — public-key, secret-key encryption — generating the public and secret keys involves a lot of multiplication of very large numbers. Even in machine learning there are many multiplication requirements. Efficient big-integer multiplication is how the machines actually do it.

Domain connection: RSA key generation multiplies pairs of primes that are hundreds of digits long; the security of the scheme rests on those multiplications being fast to do (for the key owner) while the reverse operation, factoring, is slow (for an attacker). Astronomers multiply numbers with dozens of digits when combining measurements, and machine-learning libraries multiply large integers when doing exact arithmetic — all of them rely on fast big-integer multiplication, which is what this divide-and-conquer method provides.

9.4.2 The Decimal Setup (Powers of 10)

The idea starts with a decimal observation. Take the number 1234. We can split it into a high part and a low part and write it as

$1234 = 12 \times 1 0^{2} + 34$

The 2 in $1 0^{2}$ comes from the total number of digits: 4 digits, split in half, so $4/2 = 2$ . The advantage: multiplying by a power of 10 in decimal is just adding zeros to the right — an easy, constant-time operation. If you have a number and split it in half, multiplying the high half by a power of 10 requires no real computation at all. That is why we divide the number into two halves: so that the "multiply by power of 10" parts are free.

The same split works for the second number: 5678 is $56 \times 1 0^{2} + 78$ .

The pattern in symbols. An $n$ -digit number splits into a high half $A$ and a low half $B$ , so that the number is $A \times 1 0^{n /2} + B$ . The exponent $n /2$ is exactly the length of each half. Multiplying by $1 0^{n /2}$ is appending $n /2$ zeros — an operation that costs constant time. So the expensive work of a multiplication is concentrated in the half-size multiplications $A$ times $C$ , $A$ times $D$ , and so on — the power-of-ten multiplications are effectively free.

9.4.3 Worked Example: 25 × 15

Multiply 25 by 15 using the split idea. Both numbers have two digits, so the halves are single digits:

$25 \times 15 = (2 \times 1 0^{1} + 5 \times 1 0^{0}) \times (1 \times 1 0^{1} + 5 \times 1 0^{0})$

We introduce the powers of 10 because multiplying by them is trivial — $1 \times 1 0^{1}$ is just a 1 with one zero added to its right. Now expand the brackets, multiplying first term by first term, first by second, second by first, second by second:

$25 \times 15 = 2 \times 1 \times 1 0^{1 + 1} + 2 \times 5 \times 1 0^{1 + 0} + 5 \times 1 \times 1 0^{0 + 1} + 5 \times 5 \times 1 0^{0 + 0} = 2 \times 1 0^{2} + (2 \times 5 + 5 \times 1) \times 1 0^{1} + 5 \times 5 \times 1 0^{0} = 2 \times 1 0^{2} + 15 \times 1 0^{1} + 25 = 200 + 150 + 25 = 375$

Result: 375. Sense-check: 25 × 15 = 25 × (10 + 5) = 250 + 125 = 375 — the three-term expansion agrees exactly with the direct product.

Watch what happened: we reduced the multiplication of two two-digit numbers to three additions — add two zeros to the right of 2, add one zero to the right of 15, keep 25, and add them once. Multiplication by powers of 10 is a constant-time operation (adding zeros), so the heavy work became just additions. That is the property we exploit: split the number in half so that the power-of-ten multiplications are free, and the big multiplication collapses into a few additions.

9.4.4 The General Formula: XY = AC·10ⁿ + (AD + BC)·10^(n/2) + BD

Generalize. Let $X = A B$ and $Y = C D$ , where $A B$ is an $n$ -digit number split into two halves: $A$ is the high half, $B$ is the low half — for 1234, $A = 12$ , $B = 34$ . Similarly for 5678, $C = 56$ , $D = 78$ . Then

$X = A \times 1 0^{n /2} + B, Y = C \times 1 0^{n /2} + D$

Expanding the product and combining equal powers of 10 — the distributive property, exactly as in the 25 × 15 example — gives

$X \times Y = A C \times 1 0^{n} + (A D + B C) \times 1 0^{n /2} + B D$

where $A C$ , $A D$ , $B C$ , $B D$ are the products of the halves. Each term has a name and a job:

$A C \times 1 0^{n}$ — the high product. It combines $A \times 1 0^{n /2}$ with $C \times 1 0^{n /2}$ : the two $1 0^{n /2}$ factors multiply to $1 0^{n}$ .
$(A D + B C) \times 1 0^{n /2}$ — the cross terms. They carry the shared $1 0^{n /2}$ factor.
$B D$ — the low product.

For 1234 × 5678: $A C = 12 \times 56$ , $A D = 12 \times 78$ , $B C = 34 \times 56$ , $B D = 34 \times 78$ , combined by the formula. The multiplications by $1 0^{n}$ and $1 0^{n /2}$ are just zero-appending; the real multiplications left are the four half-products.

9.4.5 The Binary Version (Powers of 2 = Left Shifts)

In binary the same idea works with powers of 2 instead of powers of 10. Each number is divided into a high half and a low half. If $I$ is an $n$ -bit number split into $I_{H}$ (high bits) and $I_{L}$ (low bits), and $J$ is split into $J_{H}$ and $J_{L}$ — for an 8-bit number, 4 and 4 bits; for a 4-bit number, 2 and 2; for 32 bits, 16 and 16 — then

$I = I_{H} \times 2^{n /2} + I_{L}, J = J_{H} \times 2^{n /2} + J_{L}$

What is the advantage of multiplying by powers of 2? In binary, multiplying by a power of 2 is nothing but a left shift: 2 is $1 0_{2}$ , 4 is $10 0_{2}$ — you just append zeros, which is a shift, a constant-time operation. So the same property we exploited in decimal — cheap multiplication by the base — holds in binary.

The slide illustrated the split with the numbers 211 and 89, each written in binary. 211 is $1101001 1_{2}$ : splitting the 8 bits into halves gives the high half $I_{H} = 110 1_{2} = 13$ and the low half $I_{L} = 001 1_{2} = 3$ . 89 is $0101100 1_{2}$ (padded to 8 bits): $J_{H} = 010 1_{2} = 5$ , $J_{L} = 100 1_{2} = 9$ . So

$211 = 13 \times 2^{4} + 3, 89 = 5 \times 2^{4} + 9$

and the product formula below expands into

$211 \times 89 = 13 \times 5 \times 2^{8} + (13 \times 9 + 3 \times 5) \times 2^{4} + 3 \times 9 = 65 \times 256 + 132 \times 16 + 27 = 16640 + 2112 + 27 = 18779$

Sense-check: $211 \times 89 = 211 \times 90 - 211 = 18990 - 211 = 18779$ — the three-term expansion agrees with the direct product.

Expanding exactly as before and combining common powers:

$I \times J = (I_{H} \times 2^{n /2} + I_{L}) \times (J_{H} \times 2^{n /2} + J_{L}) = I_{H} J_{H} \times 2^{n} + (I_{H} J_{L} + I_{L} J_{H}) \times 2^{n /2} + I_{L} J_{L}$

Here $I_{H} J_{H} \times 2^{n}$ combines the two $2^{n /2}$ factors ( $2^{n /2} \times 2^{n /2} = 2^{n}$ ), the middle term $I_{H} J_{L} + I_{L} J_{H}$ carries the two cross products with a shared $2^{n /2}$ , and $I_{L} J_{L}$ is the low product. The multiply-by- $2^{n}$ and multiply-by- $2^{n /2}$ parts are left shifts — constant time. The four half-size products $I_{H} J_{H}$ , $I_{H} J_{L}$ , $I_{L} J_{H}$ , $I_{L} J_{L}$ are the only real multiplications left, and each is a problem of the same kind with half as many bits — the recursion is ready.

Pitfall — the exponent arithmetic. The high term is $I_{H} J_{H} \times 2^{n}$ , not $2^{n /2}$ — the two half-size factors multiply: $2^{n /2} \times 2^{n /2} = 2^{n}$ . A common error is writing the high term with $2^{n /2}$ . Check the exponent by adding: the high half is multiplied by $2^{n /2}$ , so the product of the high halves carries exponent $n /2 + n /2 = n$ .

9.4.6 Recursion and Next-Class Warning

The four products $I_{H} J_{H}$ , $I_{H} J_{L}$ , $I_{L} J_{H}$ , $I_{L} J_{L}$ can themselves be large — $A B$ is large, $C D$ is large, so $A C$ is large. Each of them has to be broken down further, recursively, until we reach the last base case of constant size. That is the recursion: big multiplication breaks into half-sized multiplications, which break into quarter-sized multiplications, until the pieces are small enough to solve directly (two single bits, say, whose product is computed outright).

Cost of the recursion. Each call splits the $n$ -bit numbers in half and pays constant time for the shifts and additions (the $Θ (n)$ combine). The recurrence is

$T (n) = 4 T (\frac{n}{2}) + Θ (n)$

— four recursive half-size multiplications. With $a = 4$ , $b = 2$ , the critical exponent is $n^{l o g_{2} 4} = n^{2}$ , so $f (n) = Θ (n)$ is polynomially smaller: master theorem case 1 gives $T (n) = Θ (n^{2})$ . In other words, the naive divide-and-conquer split alone does not yet beat the schoolbook method — the gain comes from the cheap power-of-two multiplications and from the recursive structure that the professor will build on next session. (The reference treatment shows that a smarter reorganization — computing $(I_{H} - I_{L}) (J_{L} - J_{H})$ and reusing it — reduces the recursion to three half-size products, giving $T (n) = 3 T (n /2) + Θ (n)$ and $Θ (n^{l o g_{2} 3}) = O (n^{1.585})$ ; that improvement is the Karatsuba method. The professor's class version uses the four-product form above, and that is the one to master.)

Q: Will you repeat the concept next time, before the binary example? A: No. The next session will not repeat this — you must be very thorough on everything up to here. If the decimal concept is clear, the binary example will follow easily; if you are not clear, you will not follow the full walkthrough. Spend at least one hour on this before coming back.

Warning — the professor will not repeat this. The next session moves on without reviewing the decimal setup. If the split idea — write each number as high half times base to the power $n /2$ plus low half — is not fully understood in decimal, the binary walkthrough will be lost. The professor's explicit instruction: spend at least one hour on this before the next class.

Practice plan: make sure the split idea — write each number as high half times base to the power $n /2$ plus low half — is fully understood in decimal first. Understand why multiplying by powers of the base is a constant-time operation (adding zeros in decimal, left shifts in binary), and how the bracket expansion produces three combined terms: the high product, the cross terms, and the low product.

Recap and bridge: big-integer multiplication uses the same divide-conquer-recur-combine spine as the sorting algorithms — split both numbers in half, multiply the four half-pairs recursively, and combine with shift-and-add — because multiplying by a power of the base is constant time (append zeros in decimal, left-shift in binary). The three-term formula $X Y = A C \times 1 0^{n} + (A D + B C) \times 1 0^{n /2} + B D$ is the whole concept in one line; next session's binary walkthrough builds directly on it.

Exam Guidance Summary

Everything in this lecture is conceptual — programming is out of scope, and the professor stated it directly: "theory and getting marks are two different things." What follows is the complete set of exam-relevant points from the session.

Merge sort — order of execution is exam material. Expect a question about the order of execution: "give the order of execution" or "which step does this sequence arrive at in merge sort." The leftmost subarrays divide and merge completely before the right half starts. Implement merge sort, number the recursive calls, and trace it — this is compulsory practice.
Quick sort — worst case. The correct answer is: the worst case happens when the pivot is the smallest or the largest element in the subarray, giving $O (n^{2})$ time. "Already sorted or descending input" is not the accepted answer, though sorted input often goes with an extreme pivot; the fundamental issue is the extreme pivot.
Quick sort — pivot choice in the exam. Choose the first element, the median, or the last element — your choice. The median guarantees a balanced split into left and right subarrays.
Master theorem. Students are expected to know the recurrence $T (n) = a T (n / b) + f (n)$ from the earlier unit on recurrence equations and the master theorem; it will not be re-explained. Read it in English: a problem of size n is divided into a subproblems of size n/b, with f(n) the divide-and-combine time.
Analysis tools. Divide-and-conquer algorithms are analyzed with recurrence equations or the master theorem; the recursion-tree picture (work per level × tree height) is the intuitive route for merge sort.
Format of the exam. Questions are conceptual — programming is out of scope. "Theory and getting marks are two different things": conceptual understanding is what is tested; implementation is your own practice.
Base case. Know the precise definition: the case that needs no recursive call and is solved directly in constant time — not merely "where the algorithm ends."
Integer multiplication — not repeated. The professor warned that the next session will not repeat the decimal setup; the split idea (high half times base to the power $n /2$ plus low half, with $X Y = A C \times 1 0^{n} + (A D + B C) \times 1 0^{n /2} + B D$ ) must be mastered before returning, spending at least one hour on it.

Key Industry Applications

The divide-and-conquer ideas of this lecture show up across real software and hardware systems:

Real-world: merge sort is the best choice for sorting linked lists, because it needs no random access — traversal from the head matches merge sort's sequential divide-and-merge pattern.
Real-world: external sorting via external merge sort handles datasets too large for main memory — chunks are sorted into temporary files, then the sorted subfiles are merged into larger files.
Real-world: the Java Arrays.sort method uses merge sort.
Real-world: the Linux kernel uses merge sort for linked lists.
Real-world: Python's Timsort combines merge sort and insertion sort.
Real-world: big-integer multiplication via divide and conquer powers RSA-style cryptography, where public/secret key generation multiplies very large numbers; astronomy, quantum theory, and machine learning also depend on efficient multiplication of large quantities.
Real-world: the same divide, recur, conquer pattern underlies recursive algorithms across sorting, searching, and data processing in general — from databases that merge sorted runs to compilers that split and combine intermediate representations.

DSA Lecture 9 notes · Divide and Conquer

Data Structures and Algorithms· postgraduate· 2026-08-09

Sections Breakdown

1Divide and Conquer: The Strategy

The three mandatory steps — divide, recur, conquer; the master theorem recurrence T(n) = aT(n/b) + f(n), base cases, and the three master-theorem cases.

2Merge Sort

The algorithm, full worked traces, the merge step, order of execution, O(n log n) complexity, stability and other properties, and applications.

3Quick Sort

The pivot partition scheme with pointers i and j, a full worked partition, and the O(n^2) worst case caused by extreme pivots.

4Integer Multiplication by Divide and Conquer

The decimal and binary split formulas, worked examples, and the recursion into four half-size products.

Postgraduate students studying algorithm design techniques

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Divide and Conquer: The Strategy

Must-know: The master theorem recurrence read in English: a problem of size n is divided into a subproblems of size n/b, with f(n) the time for dividing and combining. The base case is the case that needs no recursive call and is solved directly in constant time — not merely 'where the algorithm ends'.

$T (n) = a T (\frac{n}{b}) + f (n)$

Top pitfall: Calling the base case 'where the algorithm ends' — ending is a consequence; the definition is that no recursive call is needed. Also forgetting the conquer (combine) step, which is mandatory.

Self-check: A recursion splits a problem of size n into 3 subproblems each of size n/2 with linear divide-and-combine cost: what are a and b, and which master-theorem case applies?

Connects to: 9.2

Merge Sort

Must-know: The order of execution of merge sort: the leftmost subarrays divide and merge completely before the right half starts; expect an exam question asking for the order of execution or the step at which a particular sequence arrives. Complexity is O(n log n): level cost n times tree height log2 n, or master theorem case 2 on T(n) = 2T(n/2) + Theta(n).

$n \cdot lo g_{2} n$

Top pitfall: Believing the merge re-compares elements of the other subarray, or that 'order of execution' means which index is used next. Also assuming merge sort is in place: writing merged elements into the first positions overwrites left-subarray elements not yet copied (the [3,4,5] + [1,2] counterexample).

Self-check: In the merge of [27, 38] with [3, 43], which element is copied first, and why is 38 never compared with 3?

Connects to: 9.1, 9.3

Quick Sort

Must-know: The worst case of quick sort happens when the pivot is the smallest or the largest element in the subarray, giving O(n^2) — 'sorted or descending input' is not the accepted answer. In the exam choose the first element, the median, or the last element as the pivot; the median guarantees a left and a right subarray.

$pivot > A [i], A [j] > pivot, i \leq j$

Top pitfall: Answering that the worst case is 'a sorted or descending array'. The cause is an extreme pivot (smallest or largest), which leaves n-1 elements in one subproblem; sorted input only becomes the worst case through the pivot position.

Self-check: On [44, 75, 23, 43, 55, 12, 64, 77, 33] with pivot 44, which two swaps occur, and where does 44 land after one partition iteration?

Connects to: 9.2, 9.1

Integer Multiplication by Divide and Conquer

Must-know: The general product formula XY = AC*10^n + (AD + BC)*10^(n/2) + BD for two split n-digit numbers, and why multiplying by powers of the base is constant time (adding zeros in decimal, left shifts in binary). The concept will not be repeated next session — the binary walkthrough builds directly on it.

$X \times Y = A C \times 1 0^{n} + (A D + B C) \times 1 0^{n /2} + B D$

Top pitfall: Writing the high product with 2^(n/2) instead of 2^n: the two half-size powers multiply, 2^(n/2) * 2^(n/2) = 2^n. Also, forgetting that only the four half-size products are real multiplications — the power-of-base multiplications are free shifts.

Self-check: Split 1234 and 5678 into halves and state the three terms AC*10^n, (AD+BC)*10^(n/2), BD with their values.

Connects to: 9.1, 9.2

Exam Guidance Summary

Must-know: The exam tests conceptual understanding only: merge sort's order of execution, quick sort's worst case (extreme pivot), the master theorem recurrence read in English, and the precise base case definition.

Top pitfall: Answering that quick sort's worst case is a sorted or descending array instead of an extreme pivot.

Self-check: Which topic did the professor say is compulsory practice even though it will not be done in class?

Connects to: 9.1, 9.2, 9.3, 9.4

Key Industry Applications

Must-know: Merge sort is the natural choice for linked lists and external sorting; Timsort merges merge sort and insertion sort; big-integer multiplication underpins RSA key generation.

Self-check: Why is merge sort the best choice for sorting a linked list?

Connects to: 9.2, 9.4

Previous LectureLecture 08 · Greedy Method

Next LectureLecture 10 · Integer Multiplication, Graph Basics, and Dijkstra's Algorithm

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

9.1 Divide and Conquer: The Strategy

9.1.1 The Three Steps: Divide, Recur, Conquer

9.1.2 Recursion, Recurrence, and the Master Theorem

9.1.3 Base Cases

9.1.4 The Three Cases of the Master Theorem

9.2 Merge Sort

9.2.1 The Algorithm

9.2.2 Worked Example: Sorting [38, 27, 43, 3, 9, 82, 10]

9.2.3 The Merge Step and a Second Example

9.2.4 Order of Execution (Depth-First)

9.2.5 Complexity Analysis: O(n log n)

9.2.6 Properties: Non-Adaptive, Stable, Not Incremental, Not Online, Not In Place

9.2.7 Applications of Merge Sort

9.2.8 Remaining Questions and Answers

9.3 Quick Sort

9.3.1 The Partition Scheme (Pivot, i, j)

9.3.2 Worked Example: Partitioning [44, 75, 23, 43, 55, 12, 64, 77, 33]

9.3.3 Complexity and the Worst Case

9.3.4 Study Expectations and Notes

9.4 Integer Multiplication by Divide and Conquer

9.4.1 Why Big-Integer Multiplication Matters

9.4.2 The Decimal Setup (Powers of 10)

9.4.3 Worked Example: 25 × 15

9.4.4 The General Formula: XY = AC·10ⁿ + (AD + BC)·10^(n/2) + BD

9.4.5 The Binary Version (Powers of 2 = Left Shifts)

9.4.6 Recursion and Next-Class Warning

Exam Guidance Summary

Key Industry Applications

DSA Lecture 9 notes · Divide and Conquer

Sections Breakdown

Exam Revision Notes

Divide and Conquer: The Strategy

Merge Sort

Quick Sort

Integer Multiplication by Divide and Conquer

Exam Guidance Summary

Key Industry Applications

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat