insertion sort

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

In the Vinony graph

Vinony's link graph records 89 inbound references to insertion sort, and connects out to sorting algorithm, merge sort and heapsort.

It sits within the topics Comparison sorts, Online sorts and Stable sorts.

Vinony links it to 40 Wikipedia language editions.

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

Instance of: online algorithm
Image: Insertion sort.gif

Show 4 more facts

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

Sources (2)

via Wikidata · CC0

~16 min read

Encyclopedic overview

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.

Excerpted from Wikipedia’s “insertion sort” article, available under the CC BY-SA 4.0 licence.