Sorting Algorithms Cheat Sheet
Sorting algorithms are non-negotiable for coding interviews. You must understand how different sorting algorithms stack up against each other - their time and space complexities and whether or not they're stable.
1) Quick Sort
Time Complexity
- Best: O(n log n)
- Average: O(n log n)
- Worst: O(n²)
Space Complexity (Worst): O(n)
2) Merge Sort
Time Complexity
- Best: O(n log n)
- Average: O(n log n)
- Worst: O(n log n)
Space Complexity (Worst): O(n)
3) Heap Sort
Time Complexity
- Best: O(n log n)
- Average: O(n log n)
- Worst: O(n log n)
Space Complexity (Worst): O(1)
4) Insertion Sort
Time Complexity
- Best: O(n)
- Average: O(n²)
- Worst: O(n²)
Space Complexity (Worst): O(1)
5) Timsort
Time Complexity
- Best: O(n)
- Average: O(n log n)
- Worst: O(n log n)
Space Complexity (Worst): O(n)
6) Bubble Sort
Time Complexity
- Best: O(n)
- Average: O(n²)
- Worst: O(n²)
Space Complexity (Worst): O(1)
7) Shellsort
Time Complexity
- Best: O(n log n)
- Average: depends on gap sequence
- Worst: O(n²)
Space Complexity (Worst): O(1)
8) Bucket Sort
Time Complexity
- Best: O(n + k)
- Average: O(n)
- Worst: O(n²)
Space Complexity (Worst): O(n)
k = number of buckets
9) Radix Sort
Time Complexity
- Best: O(nk)
- Average: O(nk)
- Worst: O(nk)
Space Complexity (Worst): O(n + k)
k = number of digits
10) Counting Sort
Time Complexity
- Best: O(n + k)
- Average: O(n + k)
- Worst: O(n + k)
Space Complexity (Worst): O(k)
k = Size of the value range
11) Selection Sort
Time Complexity
- Best: O(n²)
- Average: O(n²)
- Worst: O(n²)
Space Complexity (Worst): O(1)