Sorting algorithms: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 10: | Line 10: | ||
!Worst-case space complexity | !Worst-case space complexity | ||
|- | |- | ||
| | |Bubble sort | ||
|O(n<sup>2</sup>) | |O(n<sup>2</sup>) | ||
|O(n) | |O(n) | ||
| Line 16: | Line 16: | ||
|O(1) | |O(1) | ||
|- | |- | ||
| | |Merge sort | ||
|O(n log n) | |O(n log n) | ||
|O(n log n) | |O(n log n) | ||
| Line 22: | Line 22: | ||
|O(n) / O(1) with linked list | |O(n) / O(1) with linked list | ||
|- | |- | ||
| | |Quick sort | ||
|O(n<sup>2</sup>) | |O(n<sup>2</sup>) | ||
|O(n log n) | |O(n log n) | ||
Revision as of 07:06, 3 October 2020
Definition
Stable sort: two elements with equal keys are in the same order after sorting. For instance, insertion sort, merge sort, bubble sort are stable. Quicksort, heapsort are unstable.
Complexity
| Sorting algoritm | Worst-case performance | Best-case performance | Average performance | Worst-case space complexity |
|---|---|---|---|---|
| Bubble sort | O(n2) | O(n) | O(n2) | O(1) |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) / O(1) with linked list |
| Quick sort | O(n2) | O(n log n) | O(n log n) | O(n) / O(1) with linked list |
| Radix sort | O(kn) |