insertion sort


Also found in: Wikipedia.

insertion sort

(algorithm)
A sorting algorithm that inserts each item in the proper place into an initially empty list by comparing it with each item in the list until it finds the new element's successor or the end of the list.

Compare bubble sort.

insertion sort

A simple sorting technique that scans the sorted list, starting at the beginning, for the correct insertion point for each of the items from the unsorted list. Similar to the way people manually sort items, an insertion sort is not efficient for large lists, but is relatively fast for adding a small number of new items periodically. See sort algorithm.
References in periodicals archive ?
The method is the same as the insertion sort [1] that compares a new item with all items in parallel, then inserts the new item at the appropriate position, and shifts the existing elements in the entire multi-item vector.
Other types are rarer (see, for example, the comb sort [22] in [8], the bubble and insertion sort in [3,9], and the even-odd transition (transposition) sort in [12]).
For each language we also include small code samples, one of a regular 'Hello World' program, and another of a simple insertion sort algorithm where ever possible, so you can have a richer taste of the language.
Like Quicksort and Bubble Sort, Direct insertion sort is a comparison sort algorithm.
In this case, like the previous sort methods, direct insertion sort algorithm has a maximum polynomial time O ([n.
The algorithms include Binary Search, Selection Sort and Insertion Sort.
The insertion sort is played with similar rules and user interface as the selection sort game.
Specifically, we measure the performance of an insertion sort algorithm of O (n2) complexity on both the JavaSpaces and CORBA platforms.
We implemented a distributed, parallel insertion sort application because such an algorithm significantly exercises the CPU computationally.
Every sublist is sorted using a straightforward insertion sort.
i,k] is the number of inversions in the initial permutation of pass k, and that the insertion sort in pass k requires precisely [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] comparisons.
The film deals with three insertion sorts, three exchange sorts, and three selection sorts, beginning with insertion sorts, in which successive items of data are inserted into their correct positions relative to items previously considered.