insertion sort

sorting algorithm that, at each iteration, inserts the current input element into the suitable position between the already sorted elements

Key facts

Class: Sorting algorithm
Data structure: Array
Worst case performance: O ( n 2 ) {\displaystyle O(n^{2})} comparisons and swaps
Best case performance: O ( n ) {\displaystyle O(n)} comparisons, O ( 1 ) {\displaystyle O(1)} swaps
Average performance: O ( n 2 ) {\displaystyle O(n^{2})} comparisons and swaps
Worst case space complexity: O ( n ) {\displaystyle O(n)} total, O ( 1 ) {\displaystyle O(1)} auxiliary
Optimal: No

via Wikipedia infobox

Wikidata facts

Image: Insertion sort.gif

Show 3 more facts

Commons category: Insertion sort
name in kana: インサーションソート
Stack Exchange tag: stackoverflow.com/tags/insertion-sort

Sources (2)

via Wikidata · CC0

~16 min read

Article

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:

Simple implementation: Jon Bentley shows a version that is three lines in C-like pseudo-code, and five lines when optimized.