Sorting and Searching Algorithms: When to Use Which
Learn essential sorting and searching algorithms, their time complexities, and when to use each one. Compare quicksort, mergesort, heapsort, binary search, and more.
Why Sorting and Searching Matter
Sorting and searching are fundamental operations in every system. From displaying ranked results to finding users, these algorithms power countless features.
Interview insight: interviewers ask sorting algorithms not to test memorization, but to check if you understand trade-offs: stable vs unstable, in-place vs not, best/worst/average cases.
Comparison Sorts
The Comparison Sort Lower Bound
Any comparison-based sort has a theoretical lower bound of O(n log n). You can't sort n items faster than n log n comparisons without additional assumptions.
Merge Sort
- Time: O(n log n) always
- Space: O(n) extra
- Stable: Yes
- Use when: You need stability, external sorting (large files), and guaranteed O(n log n)
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
Quick Sort
- Time: O(n log n) average, O(n²) worst
- Space: O(log n) (recursion stack)
- Stable: No
- Use when: Average performance matters, in-memory sorting, cache-friendly
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # Middle element (not first/last)
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
Pivot selection matters: Choosing first or last element as pivot can lead to O(n²) on already sorted data. Use median-of-three or random pivot for better worst-case guarantees.
Heap Sort
- Time: O(n log n) always
- Space: O(1) (in-place)
- Stable: No
- Use when: You need guaranteed O(n log n) with O(1) space
Comparison of Comparison Sorts
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Merge Sort | n log n | n log n | n log n | n | Yes |
| Quick Sort | n log n | n log n | n² | log n | No |
| Heap Sort | n log n | n log n | n log n | 1 | No |
| Insertion Sort | n | n² | n² | 1 | Yes |
Non-Comparison Sorts
Counting Sort
- Time: O(n + k) where k is the range
- Space: O(k)
- Use when: Data is integers in a bounded range
def counting_sort(arr, max_val):
count = [0] * (max_val + 1)
result = []
for num in arr:
count[num] += 1
for i, c in enumerate(count):
result.extend([i] * c)
return result
Radix Sort
- Time: O(nk) where k is the number of digits
- Space: O(n + k)
- Use when: Sorting integers or strings with fixed length
Searching Algorithms
Linear Search
- Time: O(n)
- Use when: Unsorted data, small datasets
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1
Binary Search
- Time: O(log n)
- Use when: Sorted data
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Binary Search Variants
# Find leftmost occurrence
def bisect_left(arr, target):
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left
# Find rightmost occurrence
def bisect_right(arr, target):
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] <= target:
left = mid + 1
else:
right = mid
return left
Real-World Applications
| Scenario | Algorithm | Why |
|---|---|---|
| Database index scans | B-Tree | O(log n) range queries |
| Log search | Binary search | Sorted by timestamp |
| Ranking/sorting products | Heap sort | O(n log n) in-place |
| IP routing tables | Trie | Prefix matching |
| Batch sorting large files | External merge sort | Minimizes disk I/O |
Most languages use Timsort: Python, Java, and others use Timsort, a hybrid of merge sort and insertion sort that performs optimally on real-world data with existing runs.
What to Remember for Interviews
- Comparison sorts: Merge sort is stable, Quick sort is faster in practice
- Stable sort: Maintains relative order of equal elements
- Binary search: Requires sorted data, O(log n) time
- Non-comparison sorts: Can beat O(n log n) for special data
- Trade-offs: Time vs space, stable vs unstable, in-place vs out-of-place
Practice: Implement both merge sort and quick sort from scratch. Understanding their recursive structure and when each excels will prepare you for related follow-up questions.