Sorting
| Sorting | Time Complexity (Best) | Time Complexity (Average) | Time Complexity (Worst) | Space Complexity |
|---|---|---|---|---|
| Bubble sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Selection sort | O(n^2) | O(n^2) | O(n^2) | O(1) |
| Insertion sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Merge sort | O(n) | O(n log n) | O(n log n) | О(n) |
| Quick sort | O(n log n) | O(n log n) | O(n^2) | Depend on implementation |
| Quick sort(3 Way) | O(n) | - | - | - |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Counting sort | - | - | - | - |
1. What's the difference between merge and quick sort?