Comparison of Sorting Algorithms: Time Complexity, Space Complexity, and Stability
Key Terms:
- Stable Sort: A sorting algorithm is stable if it maintains the relative order of equal elements.
- Swap Complexity: The number of swaps an algorithm performs (important for in-place sorting).
- Space Complexity: Memory usage beyond the input array (𝑂(1) means in-place sorting).
- Best/Average/Worst Time Complexity: Describes how the algorithm performs in different cases.
| Sorting Algorithm | Best Case Time Complexity | Average Case Time Complexity | Worst Case Time Complexity | Space Complexity | Swap Complexity | Stable? | Max Info |
|---|---|---|---|---|---|---|---|
| Bubble Sort | 𝑂(𝑛) | 𝑂(𝑛²) | 𝑂(𝑛²) | 𝑂(1) | 𝑂(𝑛²) | ✅ Yes | Simple but inefficient for large datasets |
| Selection Sort | 𝑂(𝑛²) | 𝑂(𝑛²) | 𝑂(𝑛²) | 𝑂(1) | 𝑂(𝑛) | ❌ No | Always performs the same number of comparisons |
| Insertion Sort | 𝑂(𝑛) | 𝑂(𝑛²) | 𝑂(𝑛²) | 𝑂(1) | 𝑂(𝑛²) | ✅ Yes | Efficient for small or nearly sorted datasets |
| Merge Sort | 𝑂(𝑛 log 𝑛) | 𝑂(𝑛 log 𝑛) | 𝑂(𝑛 log 𝑛) | 𝑂(𝑛) | 𝑂(𝑛 log 𝑛) | ✅ Yes | Good for linked lists; requires extra space |
| Quick Sort | 𝑂(𝑛 log 𝑛) | 𝑂(𝑛 log 𝑛) | 𝑂(𝑛²) | 𝑂(log 𝑛) (in-place) | 𝑂(𝑛 log 𝑛) | ❌ No | Fastest general-purpose sort, but unstable |
| Heap Sort | 𝑂(𝑛 log 𝑛) | 𝑂(𝑛 log 𝑛) | 𝑂(𝑛 log 𝑛) | 𝑂(1) | 𝑂(𝑛 log 𝑛) | ❌ No | Used in priority queues, not stable |
| Counting Sort | 𝑂(𝑛 + 𝑘) | 𝑂(𝑛 + 𝑘) | 𝑂(𝑛 + 𝑘) | 𝑂(𝑘) | 𝑂(𝑛) | ✅ Yes | Best for small range of integers (𝑘 << 𝑛) |
| Radix Sort | 𝑂(𝑛𝑘) | 𝑂(𝑛𝑘) | 𝑂(𝑛𝑘) | 𝑂(𝑛 + 𝑘) | 𝑂(𝑛𝑘) | ✅ Yes | Good for integers and fixed-length strings |
| Bucket Sort | 𝑂(𝑛 + 𝑘) | 𝑂(𝑛 + 𝑘) | 𝑂(𝑛²) | 𝑂(𝑛 + 𝑘) | 𝑂(𝑛) | ✅ Yes | Best for uniformly distributed data |
Tags:
Leave a comment
You must be logged in to post a comment.