Sorting, Searching & Recursion.

Binary search checks the middle element, then throws away half the array on every step. If the middle is too small, the value must sit to the right, so you ignore the left half. If it is too big, you ignore the right. You repeat on the surviving half until you land on the value or run out.

That halving is where the speed comes from. A million-element array needs about twenty checks, not a million. The cost is O(log n) comparisons and O(1) extra space.

The catch is that the array must already be sorted on the key you search. On unsorted data the halving logic breaks, since a small middle no longer tells you which side to drop. This is why people sort once and then search many times.

Merge sort keeps splitting the list in half until each piece holds one element. A single element is already sorted by itself. Then it merges pairs back together, walking two sorted pieces and picking the smaller front item each time.

Merging two sorted halves is cheap because both are ordered. You compare their fronts, take the smaller one, and advance. You repeat until both are empty and one sorted run remains.

The splitting gives log n levels, and each level touches every element once, so total work is O(n log n). It needs O(n) extra room to hold the merged output. That steady cost, with no bad cases, is why merge sort is a safe default when memory is not tight.

Quicksort picks one element as a pivot, then rearranges the array so smaller items sit left of it and larger items sit right. After that single pass, the pivot is in its final sorted spot. You then sort the left and right chunks the same way.

The rearranging happens in place. You walk the array with a pointer, swapping any item smaller than the pivot toward the front. When you finish, you swap the pivot into the boundary you built.

Because it moves items within the same array, quicksort needs almost no extra memory, only O(log n) for recursion. Average speed is O(n log n). The in-place swaps and tight loops make it fast in practice, which is why many libraries use it.

Quicksort sorts in place and uses only O(log n) extra memory, while merge sort needs O(n) scratch space to hold merged runs. On large arrays that memory gap matters.

Their worst cases differ. Both average O(n log n), but quicksort can drop to O(n^2) on bad pivots, whereas merge sort holds O(n log n) always. Merge sort is also stable, keeping equal items in their original order. Plain quicksort is not.

So the choice follows your data:

• Pick quicksort for raw speed and tight memory on in-memory arrays.
• Pick merge sort when you need stability or guaranteed timing.
• Pick merge sort for linked lists and external files too.

This split is why array libraries often tune quicksort, while stable and external sorts use merging.

A stable sort keeps equal items in the same order they had before sorting. If two records share a sort key, the one that started first still comes first afterward.

This matters when you sort by more than one field. Say you sort people by first name, then by last name. A stable sort preserves the first-name order within each shared last name, so you get a two-level ordering with no extra comparison logic.

An unstable sort can swap equal keys unpredictably. You lose that earlier arrangement, and multi-pass sorting stops working. Merge sort and insertion sort are naturally stable, while plain quicksort and heapsort are not.

Most standard libraries use a hybrid sort tuned for real data, not a single textbook algorithm. Java's object sort uses Timsort, which blends merge sort with insertion sort and exploits runs that are already ordered. Python used Timsort until version 3.11 and now uses Powersort, a Timsort variant with a better rule for which runs to merge next.

C++ std::sort uses introsort, which starts as quicksort and switches to heapsort if recursion goes too deep. That switch guards against quicksort's O(n^2) worst case while keeping its usual speed.

Two patterns follow. Sorts of objects tend to be stable, often Timsort or a variant of it. Sorts of raw numbers tend to be unstable and in place, often an introsort variant.

Knowing your library's choice tells you its stability and its worst-case guarantee, so you never reimplement a sort the runtime already does well.

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. Each call handles one slice, then hands the rest to another call.

Every recursive function needs two ingredients. First, a base case, an input small enough to answer directly with no further call. Second, a recursive step that shrinks the problem and calls itself, moving toward that base case.

Miss either one and it breaks. Without a base case the calls never stop. Without real progress toward it, you also never stop.

A factorial shows both parts:

function fact(n) {
  if (n <= 1) return 1;      // base case
  return n * fact(n - 1);    // shrinks toward base
}
// fact(4) === 24

A base case is the stopping condition that returns an answer directly, without another recursive call. It is the point where the problem is small enough to solve outright, like an empty list or zero.

Without one, the function keeps calling itself forever, because the problem never shrinks to something answerable. Each call reserves a frame on the call stack for its local state. The frames pile up until the stack runs out of room, and the program crashes with a stack overflow.

A wrong base case fails the same way. If your condition never matches the values you reach, the recursion skips the exit and never stops. Getting the base case exact is the first thing to check.

Backtracking builds a solution one choice at a time and abandons a path the moment it cannot work. It explores a tree of partial choices, going deeper while things look valid and retreating when they do not.

The difference from brute force is when you check. Brute force generates every full candidate, then checks each one at the end. It never notices a doomed path early, so it wastes effort completing arrangements that were broken from the start. Backtracking tests constraints during construction and prunes dead branches before finishing them.

That early pruning is where the savings come from. On problems like placing queens or filling a grid, backtracking skips huge regions of hopeless combinations, while brute force builds and checks them all.

A greedy algorithm builds an answer step by step, always taking the option that looks best. It never revisits a choice, which keeps it fast and simple, usually O(n log n) after a sort, sometimes O(n).

Greedy works when two things hold. The first is the greedy-choice property, where a locally best pick is part of some overall best answer. The second is optimal substructure, where solving what remains after that pick gives the full solution.

Making change in US coins works greedily. You take the biggest coin that fits, 25 cents first, then 10, 5 and 1. It fails on unusual coin sets, where a smaller first coin wins.

An unproven greedy pick can return a wrong answer with no error, so test it against a slower exact method.