Top 35 Sorting & Searching Interview Questions 2025

QuickSort: average O(n log n), worst O(n²), in-place, not stable, cache-friendly. MergeSort: always O(n log n), O(n) extra space, stable, good for linked lists. QuickSort usually faster in practice (cache locality, smaller constants). Use MergeSort when: stability needed, worst-case guarantee required, external sorting (large files).

Small n (<50): Insertion sort (simple, low overhead). General purpose: QuickSort (fastest average). Guaranteed O(n log n): MergeSort. Nearly sorted: Insertion sort O(n). Limited range integers: Counting sort O(n+k). Strings/multi-key: Radix sort. Stability needed: MergeSort, TimSort. Memory limited: HeapSort (in-place).

HeapSort: build max-heap O(n), repeatedly extract max and heapify O(n log n). In-place, not stable. Build heap: heapify from n/2 down to 0. Extract: swap root with last, reduce size, heapify root. Total: O(n log n) guaranteed. Worse cache performance than QuickSort. Use when: guaranteed O(n log n) needed with O(1) space.

Binary search: O(log n) on sorted array. Basic: find exact match. Variations: lower_bound (first element >= target), upper_bound (first element > target), search insert position, find first/last occurrence. Key: handle boundaries carefully, use left < right or left <= right consistently. Template: while left < right, mid = left + (right-left)/2.

Methods: (1) Sort - O(n log n), (2) Max-heap - O(n + k log n), (3) Min-heap of size k - O(n log k), (4) QuickSelect - O(n) average, O(n²) worst. QuickSelect: partition like QuickSort, recurse only on relevant side. For guaranteed O(n): median of medians pivot selection. Min-heap good when k << n and streaming.