Sorting algorithms: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 12: | Line 12: | ||
|O(1) | |O(1) | ||
|- | |- | ||
| | |Mergesort | ||
| | |O(n log n) | ||
| | |O(n log n) | ||
| | |O(n log n) | ||
| | |O(n) / O(1) with linked list | ||
|- | |- | ||
| | |Quicksort | ||
| | |O(n<sup>2</sup>) | ||
| | |O(n log n) | ||
| | |O(n log n) | ||
| | |O(n) / O(1) with linked list | ||
|} | |} | ||
== References == | == References == | ||
Revision as of 04:50, 28 May 2018
| Sorting algoritm | Worst-case performance | Best-case performance | Average performance | Worst-case space complexity |
|---|---|---|---|---|
| Bubblesort | O(n2) | O(n) | O(n2) | O(1) |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) / O(1) with linked list |
| Quicksort | O(n2) | O(n log n) | O(n log n) | O(n) / O(1) with linked list |