Insertion Sort
By Yin-So Chen

The basic step in this algorithm is to insert a data set into a sequence of ordered (increasing) data sets in such way that the resulting sequence of data set is also ordered. Thus if the data set D is inserted in position i, then the data sets in position j less than i will be less than D, and the data sets in position j greater than i will be greater than D.

Since we will be manipulating the data sets in an array, we will have to compare all of the values of the data and move them once the ordering relationship between two values are determined. Below is the pseudo-code of the algorithm.

Insertion Sort (Sorting the array A[size])

    For index i = 2 up to i = size
        While before reach the end of cells
            Compare the element A[i]with the preceding element (A[i - 1]).
            If the element is smaller than the preceding one (A[i] < A[i - 1]),
                swap them;
            else, go to the next element.

Discuss this article in the forums

Date this article was posted to 9/13/1999
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
Sorting Algorithms

© 1999-2011 All rights reserved. Terms of Use Privacy Policy
Comments? Questions? Feedback? Click here!