Insertion Sort

If the first few objects are already sorted, an unsorted object can be inserted in the sorted set in proper place. This is called insertion sort. An algorithm consider the elements one at a time, inserting each in its suitable place among those already considered (keeping them sorted). Insertion sort is an example of an incremental algorithm. It builds the sorted sequence one number at a time. This is perhaps the simplest example of the incremental insertion technique, where we build up a complicated structure on n items by first building it on n − 1 items and then making the necessary changes to fix things in adding the last item. The given sequences are typically stored in arrays. We also refer the numbers as keys. Along with each key may be additional information, known as satellite data.

public IList InsertionSort(IList arrayToSort)
{
    for (int i = 1; i < arrayToSort.Count; i++)
    {
        object val = arrayToSort[i];
        int j = i - 1;
        bool done = false;
        do
        {
            if (((IComparable)arrayToSort[j]).CompareTo(val) > 0)
            {
                arrayToSort[j + 1] = arrayToSort[j];
                RedrawItem(j + 1);
                pnlSamples.Refresh();
                if (chkCreateAnimation.Checked)
                    SavePicture();
                j--;
                if (j < 0)
                {
                    done = true;
                }
            }
            else
            {
                done = true;
            }

        } while (!done);
        arrayToSort[j + 1] = val;
                
        RedrawItem(j + 1);
        pnlSamples.Refresh();
        if (chkCreateAnimation.Checked)
            SavePicture();
    }
    return arrayToSort;
}