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?