Sorting Algorithm Complexity
Compare time and space complexity of common sorting algorithms.
Covers bubble sort, merge sort, quick sort, and more.
Sorting Complexity Comparison
The fastest comparison-based sorting algorithms run in O(n log n) time.
No comparison sort can do better than this in the worst case.
Time Complexity Table
| Algorithm | Best Case | Average Case | Worst Case | Space |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n + k) |
Key Concepts
| Property | Meaning |
|---|---|
| Stable | Equal elements keep their original relative order |
| In-place | Uses O(1) extra memory (sorts within the array) |
| Comparison-based | Sorts by comparing pairs of elements |
| k | Range of input values (for counting/radix sort) |
Example 1
You need to sort 1 million records and memory is limited. Which algorithm is best?
Heap sort: O(n log n) time with O(1) space
It sorts in-place without needing extra arrays
Heap sort is ideal when memory is constrained but guaranteed O(n log n) is needed
Example 2
You have a nearly sorted array of 10,000 elements with only a few out of place. Which algorithm is fastest?
Insertion sort has O(n) best case on nearly sorted data
Each out-of-place element only needs a few swaps
Insertion sort is the best choice for nearly sorted data (approaches O(n))
When to Use It
Use this reference when choosing a sorting algorithm:
- Selecting the right sort for your data size and constraints
- Understanding tradeoffs between speed, memory, and stability
- Optimizing code performance in software engineering
- Preparing for technical interviews and algorithm courses