Editing Insertion sort (section)

==Relation to other sorting algorithms==
Insertion sort is very similar to [[selection sort]]. As in selection sort, after ''k'' passes through the array, the first ''k'' elements are in sorted order. However, the fundamental difference between the two algorithms is that insertion sort scans backwards from the current key, while selection sort scans forwards.  This results in selection sort making the first k elements the ''k'' smallest elements of the unsorted input, while in insertion sort they are simply the first ''k'' elements of the input.

The primary advantage of insertion sort over selection sort is that selection sort must always scan all remaining elements to find the absolute smallest element in the unsorted portion of the list, while insertion sort requires only a single comparison when the {{nowrap|(''k'' + 1)}}-st element is greater than the ''k''-th element; when this is frequently true (such as if the input array is already sorted or partly sorted), insertion sort is distinctly more efficient compared to selection sort. On average (assuming the rank of the {{nowrap|(''k'' + 1)}}-st element rank is random), insertion sort will require comparing and shifting half of the previous ''k'' elements, meaning that insertion sort will perform about half as many comparisons as selection sort on average.

In the worst case for insertion sort (when the input array is reverse-sorted), insertion sort performs just as many comparisons as selection sort. However, a disadvantage of insertion sort over selection sort is that it requires more writes due to the fact that, on each iteration, inserting the {{nowrap|(''k'' + 1)}}-st element into the sorted portion of the array requires many element swaps to shift all of the following elements, while only a single swap is required for each iteration of selection sort. In general, insertion sort will write to the array O(''n''<sup>2</sup>) times, whereas selection sort will write only O({{mvar|n}}) times. For this reason selection sort may be preferable in cases where writing to memory is significantly more expensive than reading, such as with [[EEPROM]] or [[flash memory]].

While some [[divide-and-conquer algorithm]]s such as [[quicksort]] and [[mergesort]] outperform insertion sort for larger arrays, non-recursive sorting algorithms such as insertion sort or selection sort are generally faster for very small arrays (the exact size varies by environment and implementation, but is typically between 7 and 50 elements). Therefore, a useful optimization in the implementation of those algorithms is a hybrid approach, using the simpler algorithm when the array has been divided to a small size.<ref name="pearls"/>