aloalgo.comSorting Summary
With so many sorting algorithms to choose from, how do you know which one to use? This guide focuses on the practical question: given a situation, which sorting algorithm should you reach for?Quick Reference
Here's your cheat sheet for choosing a sorting algorithm:| Situation | Best Choice | Why |
|---|---|---|
| General purpose | QuickSort | Fastest average case, in-place |
| Need stability | MergeSort | Preserves equal element order |
| Nearly sorted data | Insertion Sort | O(n) for nearly sorted |
| Linked lists | MergeSort | No random access needed |
| Small integers (0-k) | Counting Sort | O(n+k) linear time |
| Need kth element only | QuickSelect | O(n) average, no full sort |
| Memory constrained | HeapSort | O(1) extra space, guaranteed O(n log n) |
Complexity Comparison
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| QuickSort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| MergeSort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| HeapSort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes |
| Radix Sort | O(dn) | O(dn) | O(dn) | O(n+k) | Yes |
Chapters
Learn each sorting algorithm in detail:- Introduction to Sorting
- Bubble, Insertion and Selection Sort - O(n²) sorts
- Merge, Quick, and Heap Sort - O(n log n) sorts
- Radix and Counting Sort - O(n) linear time sorts
Interview Tips
- Know the trade-offs: Time vs space, stability, worst case guarantees
- Python's sorted(): Uses Timsort (hybrid of merge + insertion sort), O(n log n), stable
- Partial sorting: Use QuickSelect for kth element, heaps for top-k
- Custom comparators: Know how to sort by custom keys
- In-place requirement: QuickSort or HeapSort, not MergeSort
- Linked list sorting: Always MergeSort (no random access)
Practice Problems
Sorting ApplicationsPartition & SelectionSorted Array ProblemsFinal Thoughts
Sorting is less about memorizing algorithms and more about understanding trade-offs. In interviews, the key is quickly identifying which properties matter for your specific problem: Do you need stability? Is space constrained? Is the data nearly sorted? Is the range of values limited? Answer these questions, and the right algorithm becomes obvious.Was this helpful?
Company
Practice
Learn
© 2026 aloalgo.com. All rights reserved.