Comparison of Sorting
With so many sorting algorithms, how do you choose? Here's a comparison of the algorithms we covered.
Comparison Table
- Bubble: O(n²) time, O(1) space, stable. Simple but slow.
- Selection: O(n²) time, O(1) space, not stable. Fewer swaps.
- Insertion: O(n²) worst, O(n) best, O(1) space, stable. Good for small/nearly sorted.
- Merge: O(n log n) time, O(n) space, stable. Good for large data and stability.
- Quick: O(n log n) average, O(n²) worst, O(log n) space, not stable. Fast in practice.
- Heap: O(n log n) time, O(1) space, not stable. Guaranteed O(n log n).
- Counting: O(n + k) time, O(k) space, stable. For small integer range.
- Radix: O(d * (n + k)) time, O(n + k) space, stable. For integers/strings with fixed digits.
- Bucket: O(n + k) average, O(n²) worst, O(n) space. For uniformly distributed data.
When to use which:
- Small data: Insertion sort.
- Nearly sorted: Insertion sort.
- Large data requiring stability: Merge sort.
- General-purpose large data: Quick sort (with good pivot).
- Memory constrained: Heap sort or Quick sort.
- Integer small range: Counting sort.
- Integer with multiple digits: Radix sort.
Two Minute Drill
- No single sorting algorithm is best for all cases.
- Consider time, space, stability, input size, and distribution.
- Hybrid sorts (like Timsort) combine multiple algorithms.
- Understanding trade-offs helps you choose correctly.
Need more clarification?
Drop us an email at career@quipoinfotech.com