Sorting Algorithms
#
Sorting algorithms organize data in a specific order (ascending or descending). They vary in complexity, stability, and use cases.
Categories
#
Based on Comparison
#
- Use element comparisons to sort
- Lower bound O(n log n) for comparison sorts
- Stable: Bubble, Insertion, Merge, Tim
- In-place: Quick, Heap, Bubble, Insertion, Selection
Non-Comparison
#
- Depend on key ranges or key characteristics
- Can achieve better than O(n log n) for special cases
- Stable: Counting, Bucket, Pigeonhole
Hybrid
#
- Combine multiple strategies
- Tim Sort combines merge and insertion
Common Complexity Comparison
#
| Algorithm | Best | Average | Worst | Space | Stable |
|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting | O(n+k) | O(n+k) | O(n+k) | O(n+k) | Yes |
When to Use Which Algorithm?
#
- Small datasets (<100 elements): Insertion, Bubble, Selection
- Large random datasets: Quick (with good pivot), Merge, Heap
- Limited memory: In-place sorts (Quick, Heap)
- Stable sort needed: Merge, Bubble, Insertion
- Pre-sorted data: Insertion, Bubble (optimized versions)
- Limited range keys: Counting, Radix, Bucket
- Data types: Primitive types (Quick), Objects (Merge for stability)
Leetcode Problem Patterns
#
Implementation Tips
#
- Java Arrays.sort(): Uses Tim Sort (hybrid merge + insertion)
- Java Collections.sort(): Merge sort derivative
- Choose based on constraints: Stability, space, time
- Avoid unstable sorts when relative order matters