You might also be able to find a solution fromAI solution orcommunity posts
BFE.dev solution for Interview Question
1. What are the time and space complexity for sorting algorithms
Here is a table for common sorting algorithms.
| Algorithm | Time Complexity | Space Complexity | Stable? |
|---|---|---|---|
| Bubble Sort | Worst: O(n^2) Avg: O(n^2) | O(1) | Yes |
| Selection Sort | Worst: O(n^2) Avg: O(n^2) | O(1) | No |
| Insertion Sort | Worst: O(n^2) Avg: O(n^2) | O(1) | Yes |
| Merge Sort | Worst: O(n log n) Avg: O(n log n) | O(n) | Yes |
| Quick Sort | Worst: O(n^2) Avg: O(n log n) | O(log n) to O(n) | No (simple version) |
| Heap Sort | Worst: O(n log n) Avg: O(n log n) | O(1) | No |
| Counting Sort | Worst: O(n+k) Avg: O(n+k) | O(k) | Yes |
| Bucket Sort | Worst: O(n^2) Avg: O(n) | O(n) | Yes (with linked lists) |
| Radix Sort | Worst: O(d(n+k)) Avg: O(d(n+k)) | O(n+k) | Yes |
| Shell Sort | Worst: O(n(log n)^2) Avg: Depends on gap sequence | O(1) | No |
| Tim Sort | Worst: O(n log n) Avg: O(n log n) | O(n) | Yes |
Fun fact, Chrome uses Timsort for Array.prototype.sort() and it was not stable until Chrome 70
(ref).