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 why it feels instant. 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 winner, 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 lean on 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.

Speed differs in the tails. 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 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, guaranteed timing, or you sort linked lists or external files.

This split is why array libraries often tune quicksort while stable or external sorts reach for 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 clean two-level ordering for free.

With an unstable sort, equal keys can swap around unpredictably. You lose that earlier arrangement, and multi-pass sorting stops working. Merge sort and insertion sort are naturally stable; plain quicksort and heapsort are not. Knowing which one you have decides whether you can chain sorts to build compound orderings.

Most mature languages do not ship a single textbook sort. They ship a hybrid tuned for real data. Python and Java's object sort use Timsort, which blends merge sort with insertion sort and exploits runs that are already ordered.

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 show up everywhere. Sorts of objects tend to be stable, often Timsort. 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 steadily 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 clearly:

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. The problem never shrinks to something answerable, so the recursion has no exit.

That runaway is not harmless. Each call reserves a frame on the call stack for its local state. Endless calls pile up frames until the stack runs out of room, and the program crashes with a stack overflow.

A wrong base case bites the same way. If your condition never quite matches the values you reach, you skip the exit and fall into the same endless descent. 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 possibly work. It explores a tree of partial choices, going deeper while things look valid and retreating when they do not.

Plain brute force is blunter. It 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.

The difference is when you check. Backtracking tests constraints during construction and prunes dead branches before finishing them. Brute force tests only after building a whole candidate.

That early pruning is the whole payoff. On problems like placing queens or filling a grid, backtracking skips huge regions of hopeless combinations, while brute force grinds through all of them.

Dynamic programming solves a big problem by combining answers to smaller overlapping subproblems, and it stores each small answer so it is computed only once. That reuse is the whole point.

It fits problems with two traits. First, optimal substructure: the best answer is built from best answers to smaller pieces. Second, overlapping subproblems: the same smaller pieces show up again and again during a plain recursive solve.

When both hold, naive recursion redoes the same work exponentially. Dynamic programming caches each subproblem result, turning that blow-up into something like O(n) or O(n*m) time, traded for memory to hold the table.

Typical fits are counting paths, shortest routes, and optimal splits. If a recursive solution keeps recomputing identical calls, that repetition is the signal to reach for it.

A greedy algorithm builds an answer step by step, always grabbing the option that looks best right now. It never revisits a past choice. This makes it fast and simple, usually O(n log n) after a sort, sometimes O(n).

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

Making change with coin sizes like 1, 5, 10, 25 works greedily: take the biggest coin that fits, repeat. It fails on odd coin sets, where a smaller first coin wins.

When you cannot prove the pick is safe, greedy quietly returns a wrong answer. Test it against a slower exact method before trusting it.