Editing Best, worst and average case (section)

=== Sorting algorithms ===
{{see also|Sorting algorithm#Comparison of algorithms}}
{| class="wikitable"
|-
! Algorithm !! Data structure !! Time complexity:Best !! Time complexity:Average !! Time complexity:Worst !! Space complexity:Worst
|-
| Quick sort || Array || O(''n'' log(''n''))|| O(''n'' log(''n''))|| O(''n''<sup>2</sup>) || O(''n'')
|-
| Merge sort || Array || O(''n'' log(''n'')) || O(''n'' log(''n'')) || O(''n'' log(''n'')) || O(''n'')
|-
| Heap sort || Array || O(''n'' log(''n'')) || O(''n'' log(''n'')) || O(''n'' log(''n'')) || O(1)
|-
| Smooth sort || Array || O(''n'') || O(''n'' log(''n'')) || O(''n'' log(''n'')) || O(1)
|-
| Bubble sort || Array || O(''n'') || O(''n''<sup>2</sup>) || O(''n''<sup>2</sup>) || O(1)
|-
| Insertion sort || Array || O(''n'') || O(''n''<sup>2</sup>) || O(''n''<sup>2</sup>) || O(1)
|-
| Selection sort || Array || O(''n''<sup>2</sup>) || O(''n''<sup>2</sup>) || O(''n''<sup>2</sup>) || O(1)
|-
| Bogo sort || Array || O(''n'') || O(''n'' ''n''!) || O(∞) || O(1)
|}
[[File:Comparison computational complexity.svg|thumb|Graphs of functions commonly used in the analysis of algorithms, showing the number of operations ''N'' versus input size ''n'' for each function]]
* [[Insertion sort]] applied to a list of ''n'' elements, assumed to be all different and initially in random order. On average, half the elements in a list ''A''<sub>1</sub> ... ''A''<sub>''j''</sub> are less than element ''A''<sub>''j''+1</sub>, and half are greater. Therefore, the algorithm compares the (''j''&nbsp;+&nbsp;1)<sup>th</sup> element to be inserted on the average with half the already sorted sub-list, so ''t''<sub>''j''</sub> = ''j''/2. Working out the resulting average-case running time yields a quadratic function of the input size, just like the worst-case running time.
* [[Quicksort]] applied to a list of ''n'' elements, again assumed to be all different and initially in random order. This popular [[sorting algorithm]] has an average-case performance of O(''n''&nbsp;log(''n'')), which contributes to making it a very fast algorithm in practice. But given a worst-case input, its performance degrades to O(''n''<sup>2</sup>). Also, when implemented with the "shortest first" policy, the worst-case space complexity is instead bounded by&nbsp;O(log(''n'')).
* Heapsort has O(n) time when all elements are the same. Heapify takes O(n) time and then removing elements from the heap is O(1) time for each of the n elements. The run time grows to O(nlog(n)) if all elements must be distinct.
* [[Bogosort]] has O(n) time when the elements are sorted on the first iteration. In each iteration all elements are checked if in order. There are n! possible permutations; with a balanced random number generator, almost each permutation of the array is yielded in n! iterations. Computers have limited memory, so the generated numbers cycle; it might not be possible to reach each permutation. In the worst case this leads to O(∞) time, an infinite loop.