Content deleted Content added
rm spam from multiple pages : academicearth |
... previous statement was not true - what if you have an ordered list? python's timsort has an optimization for this. |
||
Line 9:
Sorting algorithms used in [[computer science]] are often classified by:
* [[Computational complexity theory|Computational complexity]] ([[Worst-case performance|worst]], [[Average performance|average]] and [[Best-case performance|best]] behaviour) of element comparisons in terms of the size of the list <math>\left( n \right)</math>. For typical sorting algorithms good behavior is [[Big O notation|<math>\mathcal{O}</math>]]<math>\left( n \log n\right)</math> and bad behavior is <math>\mathcal{O}\left( n^2 \right)</math>. (See [[Big O notation]]) Ideal behavior for a sort is <math>\mathcal{O}\left( n \right)</math>. [[Comparison sort]]s, sort algorithms which only access the list via an abstract key comparison operation,
* [[Computational complexity theory|Computational complexity]] of swaps (for "in place" algorithms).
* Memory usage (and use of other computer resources). In particular, some sorting algorithms are "[[In-place algorithm|in place]]". This means that they need only <math>\mathcal{O}(1)</math> or <math>\mathcal{O}(\log n)</math> memory beyond the items being sorted and they don't need to create auxiliary locations for data to be temporarily stored, as in other sorting algorithms.
| |||