Insertion sort
E459517
Insertion sort is a simple comparison-based sorting algorithm that builds a sorted list one element at a time by inserting each new element into its proper position.
Statements (47)
| Predicate | Object |
|---|---|
| instanceOf |
comparison-based algorithm
ⓘ
in-place algorithm ⓘ sorting algorithm ⓘ stable sorting algorithm ⓘ |
| advantage |
good performance on nearly sorted inputs
ⓘ
good performance on small inputs ⓘ simple implementation ⓘ |
| basedOn | building a sorted prefix of the array ⓘ |
| bestCaseInput | already sorted array ⓘ |
| category | simple quadratic-time sorting algorithms ⓘ |
| commonlyTaughtIn | introductory algorithms courses ⓘ |
| commonlyUsedFor | teaching sorting concepts ⓘ |
| comparedWith |
bubble sort
ⓘ
merge sort ⓘ quick sort ⓘ selection sort ⓘ |
| dataStructureSorted |
array
ⓘ
list ⓘ |
| disadvantage | quadratic time on large random inputs ⓘ |
| isAdaptive | true ⓘ |
| isInPlace | true ⓘ |
| isStable | true ⓘ |
| maintains | a growing sorted prefix ⓘ |
| numberOfShiftsWorstCase | O(n^2) ⓘ |
| oftenUsedInside | hybrid sorting algorithms ⓘ |
| origin | early computer era sorting methods ⓘ |
| processesElements | left to right ⓘ |
| requires | sequential access ⓘ |
| sortingOrder |
non-decreasing
ⓘ
non-increasing ⓘ |
| spaceComplexityWorstCase | O(1) ⓘ |
| suitableFor |
nearly sorted data
ⓘ
online sorting ⓘ small arrays ⓘ |
| supports | online algorithm behavior ⓘ |
| timeComplexityBestCase | O(n) ⓘ |
| timeComplexityWorstCase | O(n^2) ⓘ |
| typicalImplementationLanguage |
C
NERFINISHED
ⓘ
C++ NERFINISHED ⓘ Java NERFINISHED ⓘ Python NERFINISHED ⓘ |
| usedAsBaseCaseFor |
merge sort implementations
ⓘ
quick sort implementations ⓘ |
| uses |
comparison operations
ⓘ
element insertion ⓘ |
| worksBy | inserting each element into its correct position in the sorted part ⓘ |
| worstCaseInput | reverse sorted array ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.