4.17 Recursive Searching and Sorting

What you need to know

• Recursive binary search: the same halving as the loop version, but each half-search is a recursive call with updated low/high. Base case: low > high (not found) or the middle matches.
• Merge sort: split the array in half, recursively sort each half, then merge the two sorted halves into one sorted array.
• The merge step walks through both halves with two indices, copying the smaller front element each time, then copying any leftovers.
• Merge sort's base case is a sub-array of one element (already sorted).
• Merge sort is faster than selection or insertion sort for large inputs — roughly n log n operations instead of n². It needs extra memory for the temporary merged array.
• The exam may show the array at some stage of merge sort (halves sorted, not yet merged) and ask which stage or which algorithm.
• Both algorithms illustrate divide and conquer: split, solve pieces recursively, combine.

Worked example

public static int bs(int[] a, int t, int low, int high)
{
    if (low > high) return -1;             // base: not found
    int mid = (low + high) / 2;
    if (a[mid] == t) return mid;          // base: found
    if (a[mid] < t) return bs(a, t, mid + 1, high);
    return bs(a, t, low, mid - 1);
}

// merge sort on {8, 3, 5, 1}:
//   split → {8, 3} and {5, 1}
//   sort each → {3, 8} and {1, 5}
//   merge → compare 3 vs 1 → 1; 3 vs 5 → 3; 8 vs 5 → 5; leftover 8
//   result {1, 3, 5, 8}

Going deeper

The nuance, edge cases, and connections that turn a 3 into a 5.

• Recursive binary search takes the range as parameters: bs(a, target, low, high). Base cases: low > high → −1; a[mid] == target → mid. Otherwise recurse on one half. Same comparisons as the iterative version; the exam may show either.
• Merge sort: if the range has ≤ 1 element, done. Otherwise split at the middle, sort each half recursively, merge. The recursion goes all the way down to single elements before any merging happens.
• Merge step: two indices, one per half, walking forward. Compare the elements at the indices, copy the smaller into the output, advance that index. When one half runs out, copy the rest of the other. This produces a sorted combination of two sorted inputs.
• Snapshots: after the recursive sorts and before the final merge, each half is sorted independently — that's the identifying state. During the merge, the output fills left to right with the globally smallest remaining.
• Efficiency: log₂ n levels of splitting, each level does n work merging → n log n total. For n = 1,000,000: ~20 million operations vs. ~500 billion for selection sort.
• Cost: merge sort needs a temporary array of size n. Selection/insertion sort in place. Space vs. time trade-off.
• Divide and conquer is the general name: split the problem, solve pieces recursively, combine. Binary search (discard half), merge sort (sort halves and merge), and many others share the pattern.
• You trace these; you don't write them. Know what each stage looks like and how many operations each takes.

Mistakes that cost points

• Thinking merge sort merges before both halves are sorted. Recursion completes first.
• Picking a snapshot where halves aren't independently sorted as "before the merge." Both halves must be sorted.
• Saying merge sort uses less memory. More. It's faster, not smaller.

Practice questions

Written in the style of the real exam. Try each one before revealing the answer.