Recursive Searching and Sorting

⚠ Optional chapter. Combines Lessons 28.1-28.3: the same searching/sorting ideas, rewritten recursively.

Recursive Binary Search

The iterative binary search from Lesson 28.1 tracks left/right bounds in loop variables. A recursive version instead passes the shrinking range as parameters, with the range itself doing the job a while loop's condition did before:

public static int recursiveBinarySearch(int[] elements, int start, int end, int target)
{
    if (end < start)                          // base case 1: range is empty — not found
    {
        return -1;
    }
    int middle = (start + end) / 2;
    if (target == elements[middle])            // base case 2: found it
    {
        return middle;
    }
    else if (target < elements[middle])
    {
        // search the left half
        return recursiveBinarySearch(elements, start, middle - 1, target);
    }
    else
    {
        // search the right half
        return recursiveBinarySearch(elements, middle + 1, end, target);
    }
}

This has two base cases: a match at the middle, or an exhausted range. Removing the end < start check wouldn't cause a true infinite loop — Java would run out of room first: a not-found search keeps calling itself into an already-empty range until it crashes with StackOverflowError (or, if the array is empty to begin with, an immediate ArrayIndexOutOfBoundsException) — exactly the missing-base-case bug from Lesson 28.3.

Merge Sort: A Third Sorting Algorithm

Selection sort and insertion sort (Lesson 28.2) both cost roughly n² in the worst case. Merge sort is a divide-and-conquer algorithm — like binary search, it splits the problem in half repeatedly, which makes it substantially faster on large data (roughly n log n instead of n²):

Split the array into two halves.
Recursively sort each half (a single-element array is trivially already sorted — the base case).
Merge the two now-sorted halves back together, in order.

public static void mergeSort(int[] elements)
{
    int n = elements.length;
    int[] temp = new int[n]; // scratch space used during merging
    mergeSortHelper(elements, 0, n - 1, temp);
}

private static void mergeSortHelper(int[] elements, int from, int to, int[] temp)
{
    if (from >= to) return; // base case: a range of 0 or 1 elements is already sorted
    int middle = (from + to) / 2;
    mergeSortHelper(elements, from, middle, temp);      // recursively sort the left half
    mergeSortHelper(elements, middle + 1, to, temp);    // recursively sort the right half
    merge(elements, from, middle, to, temp);            // combine the two sorted halves
}

merge itself isn't recursive — it's the ordinary loop-based step that does the actual combining, using temp as scratch space so it isn't overwriting the very values it still needs to compare:

private static void merge(int[] elements, int from, int mid, int to, int[] temp)
{
    int i = from;     // next unmerged element in the left half
    int j = mid + 1;  // next unmerged element in the right half
    int k = from;      // next open slot in temp

    while (i <= mid && j <= to)
    {
        if (elements[i] <= elements[j])
        {
            temp[k++] = elements[i++];
        }
        else
        {
            temp[k++] = elements[j++];
        }
    }
    while (i <= mid)   // copy over whatever's left of the left half
    {
        temp[k++] = elements[i++];
    }
    while (j <= to)    // copy over whatever's left of the right half
    {
        temp[k++] = elements[j++];
    }
    for (int m = from; m <= to; m++) // copy the merged range back into elements
    {
        elements[m] = temp[m];
    }
}

merge walks both sorted halves with two pointers (i for the left half, j for the right), always taking the smaller of the two elements it's currently pointing at into temp. Once one half runs out, whatever's left of the other half is already in order, so it just gets copied straight over. The last step copies the merged range from temp back into elements, since elements is the array being sorted in place.

Tracing the split-then-merge structure for {86, 3, 43, 5}, using nested braces:

Split:  { {86, 3} , {43, 5} }
Split:  { { {86}, {3} } , { {43}, {5} } }   <- single elements: base case reached
Merge:  { {3, 86} , {5, 43} }
Merge:  { 3, 5, 43, 86 }

Like selection sort, merge sort's structure doesn't depend on the input's initial order — it always splits and merges the same way. But because its divide-and-conquer approach scales so much better than n² sorting, it's the fastest of the three algorithms in this curriculum, most of the time, especially as the data set grows.

Iterative vs. Recursive: Same Algorithm, Different Shape

Binary search exists in both forms (Lesson 28.1's iterative version, this lesson's recursive one) — a good concrete reminder of Lesson 28.3's point that many algorithms can be written either way. Iteration is usually preferred in real code (no risk of StackOverflowError, generally a bit more efficient) — but a recursive version can be more compact and can make a divide-and-conquer structure (like merge sort's) much more natural to express than an iterative equivalent would be.

(Aside: like Lesson 28.1's (left + right) / 2, this lesson's (start + end) / 2 and (from + to) / 2 have the same theoretical overflow-safe alternative, left + (right - left) / 2.)

Common Pitfalls

Forgetting either base case in recursive binary search. Both the "found it" and "range exhausted" cases are needed — missing the exhausted-range check risks infinite recursion on a not-found search.
Merging without first ensuring both halves are actually sorted. Merge sort's merge step assumes its two inputs are already individually sorted — that's exactly what the recursive calls before it guarantee.
Assuming recursive is always "better" than iterative, or vice versa. Each has real tradeoffs (stack depth risk vs. code clarity) — the right choice depends on the specific algorithm and data size.

Key Takeaways

Recursive binary search replaces loop-tracked bounds with a shrinking range passed as parameters, and needs two base cases: a match, or an exhausted range.
Merge sort is a recursive, divide-and-conquer sort: split in half, recursively sort each half (base case: 1 element), then merge the sorted halves back together.
Merge sort scales better than selection/insertion sort on large data (n log n vs. n²), and its performance doesn't depend on the input's initial order.
The same algorithm can often be written iteratively or recursively — the choice is a real tradeoff, not a universal "better" answer either way.

Derived from csawesome-2026: unit-4-data-collections/4.17-recursive-searching-and-sorting.md (CSA 4.17)