Describing Sorting & Searching
Bubble sort, merge sort, quicksort, binary search, linear search — vocabulary for code review and documentation
Sorting & searching vocabulary
- Bubble sort O(N²) — educational only; use built-in sort() in production
- Merge sort / Timsort O(N log N) — stable, predictable; built into Python/Java sorted()
- Binary search O(log N) — requires sorted input; returns index or -1
- Linear search O(N) — works on unsorted arrays; checks each element in order
- "Iterates through one by one" → linear; "discards half each step" → binary
Question 0 of 5
A code review comment says: "This uses bubble sort — swap adjacent elements repeatedly until sorted." When would this be an acceptable choice?
- Bubble sort — O(N²); swap adjacent elements; fine for N < 10 or educational code; never in production data pipelines
- Merge sort — O(N log N); divide and conquer; stable; good for linked lists and external sorting
- Quicksort — O(N log N) average, O(N²) worst; in-place; fastest in practice for arrays; built into most stdlib sort()
- Timsort — Python's sort() and Java Arrays.sort() for objects; hybrid merge+insertion; O(N log N); excellent on real-world data
A function is described as: "Performs binary search on a sorted array to find the target value." What is the key precondition for binary search to work correctly?
- Binary search — O(log N); compares target to midpoint; discards the half where target cannot be; requires sorted input
- Linear search — O(N); checks every element; works on unsorted arrays; use when array is small or unsorted
- Midpoint calculation:
mid = left + (right - left) / 2(avoids integer overflow vs(left + right) / 2)
How would you describe what this function does to a non-technical stakeholder?function findUser(users, targetId) {
for (let i = 0; i < users.length; i++) {
if (users[i].id === targetId) return users[i];
}
return null;
}
- "iterates through" or "goes through one by one" → linear/sequential scan
- "returns the first match" → early exit, does not scan all elements if found early
- "returns null/None/undefined" → the "not found" sentinel value
A PR description says: "Switched from insertion sort to merge sort for the report generator." What does this imply about the data size?
- Insertion sort — O(N²) worst/average; O(N) on nearly sorted data; great for tiny arrays (<50 elements); stable
- Merge sort — O(N log N) always; stable; predictable; uses O(N) extra memory
A function docstring says: "Returns the index of the target in O(log N) time; returns -1 if not found." Which algorithm does this describe?
- O(1) → hash map lookup, array index access
- O(log N) → binary search, balanced BST lookup
- O(N) → linear search, single array pass
- O(N log N) → merge sort, quicksort (average), heapsort
- O(N²) → bubble sort, insertion sort (worst), comparing all pairs