Time Complexity Overview
In C++, sorting is a fundamental concept used in almost every real-world application — from organizing data structures to optimizing search and processing operations. C++ offers both built-in sorting functions (like std::sort and std::stable_sort) and supports manual implementation of various sorting algorithms.
Each sorting algorithm has its strengths and weaknesses, and its performance depends on factors such as:
- Data size
- Data distribution
- Memory usage
- Stability requirements
Understanding the time complexity of each algorithm is crucial for selecting the right one for a given task.
Sorting Algorithm Time Complexity Table
| Algorithm | Best Case | Average Case | Worst Case | Space | Stable | In-place |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ Yes | ✅ Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | ❌ No | ✅ Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ Yes | ✅ Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ Yes | ❌ No |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ No | ✅ Yes |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ No | ✅ Yes |
| Shell Sort | O(n log n) | O(n^3/2) | O(n²) | O(1) | ❌ No | ✅ Yes |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | ✅ Yes | ❌ No |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n + k) | ✅ Yes | ❌ No |
| Bucket Sort | O(n + k) | O(n + k) | O(n²) | O(n + k) | ✅ Yes | ❌ No |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | ✅ Yes | ❌ No |
n= number of elementsk= range of input (for Counting, Bucket, Radix)- Timsort is used internally in
std::stable_sort(via Merge Sort) in many STL implementations
Stable vs In-place
- Stable: Preserves the relative order of equal elements (important in multi-key sorting).
- In-place: Uses only constant additional memory (excluding recursion stack for some algorithms).
