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.