Insertion Sort

Description

Assuming there are N data items to sort, this algorithm steps through the data set N times (in other words, makes N passes). In each pass, it takes the next unsorted item in the array and figures out where it should go among the items that are already sorted. After 4 passes, the first 4 items are in sorted order; after 10 passes, the first 10 items are in sorted order; after all N passes, all N items are in sorted order.

Animation

The Visual Sort section of this page contains small-scale, step-by-step animations of several sorting algorithms.

• Choose Insertion Sort in the first drop-down menu.
• Repeatedly click on Step until you have a sense of how the algorithm works. Then click Run and check whether its continued behavior is what you expect.
• You can click on the New Sort button to get a new set of random data if you want to repeat the process to understand the algorithm better.

Performance

On average, the "figure out where it should go" computation in each pass has to look at N/4 previously sorted items. Since that is done in all N passes, the algorithm takes approximately N * N/4 steps to go from completely unsorted data to sorted data.

Code

    // Insertion Sort: In each pass, insert another item into the sorted
    // items in front of it, in sorted order.
    void sort(int[] data, int numItems)
    {
        // In each pass, nextToSort is the index of the item to insert into
        // the sorted items that precede it.  (Nothing precedes index 0.)
        for ( int nextToSort = 1; nextToSort < numItems; nextToSort++ )
        {
            // Look backwards to see where to insert the next item.
            int dataToInsert = data[nextToSort];
            int index;
            for ( index = nextToSort - 1; index >= 0; index-- )
            {
                // If this item is bigger than the item to insert,
                // shift it up by one.
                if ( data[index] > dataToInsert )
                {
                    data[index+1] = data[index];
                }
                else
                    break;  // Break out of loop.
            }
            // data[index] <= dataToInsert OR index == -1
            data[index+1] = dataToInsert;
        }
    }