Recursive Searching and Sorting
Introduced| English | Meaning |
|---|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | Solving a problem by splitting it into smaller subproblems, solving them and combining their results. |
| merge sort/mɜːdʒ sɔːt/ | merge sort |
| merge/mɜːdʒ/ | Combining items from separate collections into one collection, often preserving a required ordering. |
Recursion meets search and sort
- The same divide-and-conquer 分治 idea powers recursive binary search and merge sort 归并排序.
- Split the problem in half, solve the halves, combine.
- Recursive binary search searches one half by calling itself on it.
- Merge sort sorts each half, then merges the sorted halves together.
Recursive binary search
- Base case: an empty range means the target is not found.
- Look at the middle. If it's the target, return its index.
- If the target is smaller, recurse on the left half; if larger, the right half.
- Each call halves the range — the same
O(log n), written recursively.
Merge sort
- Split the array into two halves; sort each half recursively.
- Base case: an array of 0 or 1 element is already sorted.
- Merge 合并: walk both sorted halves, always taking the smaller front element.
- Much faster than the
n²sorts — aboutn log nwork.
Why divide-and-conquer wins
- Halving the problem each step gives the
log nfactor. - Merge sort's
n log nbeats selection/insertion sort'sn²on large arrays. - The base case (empty or one element) stops every branch.
- Same shape as all recursion: split down, combine back up.
Recursive binary search recurses on ONE half (the target is only on one side); merge sort recurses on BOTH halves and then merges them. Both need a base case — an empty range means "not found" for search; a 0-or-1-element array is already sorted for merge sort. Divide-and-conquer is what makes them fast (O(log n) and O(n log n)).
Merge-sorting [3, 1, 2, 4]:
- Split into
[3, 1]and[2, 4]; sort each →[1, 3]and[2, 4]. - Merge: take 1, then 2, then 3, then 4 →
[1, 2, 3, 4]. - Each merge picks the smaller front element in turn.
Recursive binary search recurses on one half (base case: empty range = not found) for O(log n) search. Merge sort recurses on both halves and merges them (base case: 0 or 1 element) for O(n log n) sorting. Both are divide-and-conquer: split down, combine back up — much faster than n².
Merge sort splits into halves, then merges up
Single elements are sorted (base case); merges combine them upward.
Recursive binary search recurses on...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The target is only on one side of the middle.
Merge sort recurses on...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Sort each half, then merge the two sorted halves.
The base case for merge sort is an array of...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
One (or zero) element needs no sorting.
Merge sort's running time is about...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
log n levels of splitting, n work per level.
Both recursive binary search and merge sort are divide-and-conquer algorithms.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Both split the problem in half and recurse.
Order the merge step for halves [1,3] and [2,4].
Difficulty 3/5 · 200 coins + a small bonus on first completion today
Always take the smaller front element: 1, 2, 3, 4.