Editing Sorting algorithm (section)

=== Simple sorts ===
Two of the simplest sorts are insertion sort and selection sort, both of which are efficient on small data, due to low overhead, but not efficient on large data. Insertion sort is generally faster than selection sort in practice, due to fewer comparisons and good performance on almost-sorted data, and thus is preferred in practice, but selection sort uses fewer writes, and thus is used when write performance is a limiting factor.

==== Insertion sort ====
{{Main|Insertion sort}}
''[[Insertion sort]]'' is a simple sorting algorithm that is relatively efficient for small lists and mostly sorted lists, and is often used as part of more sophisticated algorithms. It works by taking elements from the list one by one and inserting them in their correct position into a new sorted list similar to how one puts money in their wallet.<ref>{{cite book |last=Wirth |first=Niklaus |author-link=Niklaus Wirth |title=Algorithms & Data Structures |place=Upper Saddle River, NJ |publisher=Prentice-Hall |year=1986 |isbn=978-0130220059 |pages=76–77}}</ref> In arrays, the new list and the remaining elements can share the array's space, but insertion is expensive, requiring shifting all following elements over by one. [[Shellsort]] is a variant of insertion sort that is more efficient for larger lists.

==== Selection sort ====
{{Main|Selection sort}}
''Selection sort'' is an [[in-place]] [[comparison sort]]. It has [[Big O notation|O]](''n''<sup>2</sup>) complexity, making it inefficient on large lists, and generally performs worse than the similar [[insertion sort]]. Selection sort is noted for its simplicity and also has performance advantages over more complicated algorithms in certain situations.

The algorithm finds the minimum value, swaps it with the value in the first position, and repeats these steps for the remainder of the list.<ref>{{harvnb|Wirth|1986|pp=79–80}}</ref> It does no more than ''n'' swaps and thus is useful where swapping is very expensive.