Sorting Algorithms
Practice & Revision
Sorting pattern recognition decision tree, cheat sheet, and Top 15 must-solve sorting interview problems.
1. Introduction
This section serves as your launchpad for coding interviews. Sorting is rarely asked as a standalone task (e.g., "Implement Merge Sort"). Instead, sorting is a prerequisite step that unlocks efficient solutions for interval merging, binary searches, sweep-line algorithms, and greedy choices.
2. Sorting Decision Tree
Use this guide to identify which sorting algorithm or pattern fits your problem constraints:
3. Revision Cheat Sheet
Complexity Comparison Quick-Reference
| Algorithm | Best Time | Average Time | Worst Time | Space Complexity | Stable? | Key Interview Attribute |
|---|---|---|---|---|---|---|
| Insertion Sort | O(N) | O(N²) | O(N²) | O(1) | Yes | Excellent for small arrays (N \le 16) |
| Merge Sort | O(N log N) | O(N log N) | O(N log N) | O(N) | Yes | Stable, guaranteed speed, best for linked lists |
| Quick Sort | O(N log N) | O(N log N) | O(N²) | O(log N) | No | Fast in-place partitioning, cache-friendly |
| Heap Sort | O(N log N) | O(N log N) | O(N log N) | O(1) | No | Guaranteed O(N log N) in-place without recursion |
| Counting Sort | O(N + K) | O(N + K) | O(N + K) | O(K) | Yes | Non-comparison, fast for small range bounds |
4. Top 15 Must-Solve Sorting & Selection Problems
5. Problem-Solving Framework
When confronted with a sorting-related question, follow this 3-step checklist:
1. Check Range and Type Constraints:
- Are elements floating points or values bounded by tiny bounds (e.g. [0..100])? If bounded, use Counting Sort.
- Are you asked to find the "K-th element"? Avoid sorting the whole collection; use Quick Select.
2. Determine Comparator Logic:
- If ordering records by complex relationships (e.g. string concatenation in Largest Number), write a custom comparator: (a, b) -> (b + a).compareTo(a + b).
3. Handle Intervals via Boundary Sweeping:
- For interval intersections or room meetings, sort by start time, then track overlapping boundaries using end times.
6. Quiz
Question 1: If you need to find the K-th smallest element in an array, what is the best complexity target?
Answer:O(N) average time complexity using the Quick Select algorithm, which avoids sorting the entire array.
Question 2: Why do interval merging algorithms sort by start times first?
Answer: Sorting by start times ensures that overlapping intervals are adjacent to each other in the array, allowing you to merge all overlaps in a single linear scan ofO(N) time.
Question 3: How does the Boyer-Moore Majority Vote algorithm avoid sorting the array in the "Majority Element" problem?
Answer: If a majority element exists (frequency> N/2), we can track a candidate and a balance counter. Increment counter when matching candidate, decrement when different. The majority element is guaranteed to remain as candidate, running in O(N) time and O(1) space, beating O(N log N) sorting.
Question 4: Under what circumstance would you choose Heap Sort over Quick Sort?
Answer: When you need a guaranteed worst-case time complexity ofO(N log N) combined with strictly O(1) auxiliary space (e.g., in critical safety-critical embedded systems where memory allocation is forbidden).
Question 5: What is the optimal time complexity to merge two pre-sorted arrays of sizes N and M?
Answer:O(N + M) using a two-pointer merge approach, which does not require re-sorting.