Sorting and Recursion

A recursive function solves a problem by calling itself on a smaller version of it. It needs two parts: a base case that answers directly (an empty list is sorted) and a recursive step that shrinks the input and combines the results. Divide and conquer is the most common shape: split the input into pieces, solve each piece recursively, then combine.

The running time satisfies a recurrence. If you split into $a$ subproblems of size $n/b$ and spend $O(n^d)$ splitting and combining, then $T(n) = a\,T(n/b) + O(n^d)$, and the master theorem reads off the answer by comparing $d$ with $\log_b a$:

Three recurrences come up again and again. Merge sort is $2T(n/2) + O(n)$: here $d = 1 = \log_2 2$, so $O(n \log n)$. Binary search is $T(n/2) + O(1)$: $d = 0 = \log_2 1$, so $O(\log n)$. A routine that makes one linear pass and then recurses into only one half is $T(n/2) + O(n)$: $d = 1 > 0$, so $O(n)$, because the work shrinks geometrically ($n + n/2 + n/4 + \dots \le 2n$).

One practical limit in Python: the default recursion depth is 1000. Halving recursion on a million elements goes about 20 levels deep and is fine. Recursion that peels off one element at a time on $10^5$ elements raises RecursionError, so write that version as a loop.