-
Insertion sort compareselements to the left of the current element, and inserts the current element in the correct position.
-
It has an O(n^2) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar selection sort.
| Algorithm | Best Case | Average Case | Worst Case | Space Complexity |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Selection | O(n^2) | O(n^2) | O(n^2) | O(1) |
| Insertion | O(n) | O(n^2) | O(n^2) | O(1) |
| Recursion | O(n log n) | O(n log n) | O(n^2) | O(n) |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick | O(n log n) | O(n log n) | O(n^2) | O(log n) |