Insertion Sort

The implementation of insertion sort is very well known, but to improve upon the standard description this method uses System.Collections.ObjectModel.IComparable, allowing it to sort a range of types, and the class and methods are marked as static.  Both modifications make the methods more reusable than in typical examples.

            IComparable[] start = new IComparable[] {44, 2,4,1,6,7,33,25,5,2};
            IComparable[] result = InsertionSort.Sort(start);

            IComparable[] startAlpha = new IComparable[] { "r", "A", "z", "c", "a", "h"};
            IComparable[] resultAlpha = InsertionSort.Sort(startAlpha);

The two lower routines are useful for quick sort, in that they will handle portions of arrays

Class

static class InsertionSort
    {
        /// <summary>
        /// Given a list of items, sorts by
        /// 1. examining each item from first position
        /// 2. calls method to insert value at correct sorted position
        /// </summary>
        /// <param name="startingList"></param>
        /// <returns></returns>
        public static IComparable[] Sort(IComparable[] startingList)
        {
            int arrayLength = startingList.Length;
            for (int counter = 0; counter < arrayLength; counter++)
            {
                startingList = Insert(startingList, counter);
            }
            return startingList;
        }

        /// <summary>
        /// 1. moves each value that is larger than current item's value back one
        /// 2. finaly inserting value at the correct position
        /// </summary>
        /// <param name="list"></param>
        /// <param name="position"></param>
        /// <returns></returns>
        private static IComparable[] Insert(IComparable[] list, int position)
        {
            int counter = position - 1;
            IComparable value = list[position];
            while (counter >= 0 && (list[counter].CompareTo(value) > 0))
            {
                list[counter + 1] = list[counter];
                counter = counter - 1;
            }
            list[counter + 1] = value;
            return list;
        }

        /// <summary>

        /// Given a list of items, sorts by
        /// 1. examining each item from starting index to endIndex, not necessarily the end of arry
        ///    - starting/ending indexes alllow this to be used with quick sort and portions of arrays
        /// 2. calls method to insert value at correct sorted position
        /// </summary>
        /// <param name="startingList"></param>
        /// <param name="startIndex"></param>
        /// <param name="endIndex"></param>
        /// <returns></returns>
        public static int[] Sort(int[] startingList, int startIndex, int endIndex)
        {
            for (int counter = startIndex; counter <= endIndex; counter++)
            {
                startingList = Insert(startingList, counter);
            }
            return startingList;
        }

        /// <summary>
        /// 1. moves each value that is larger than current item's value back one
        /// 2. finaly inserting value at correct position for value
        /// </summary>
        /// <param name="list"></param>
        /// <param name="position"></param>
        /// <returns></returns>
        private static int[] Insert(int[] list, int position)
        {
            int counter = position-1;
            int value = list[position];
            while (counter >= 0 && (list[counter].CompareTo(value) > 0))
            {
                list[counter + 1] = list[counter];
                counter = counter - 1;
            }
            list[counter + 1] = value;
            return list;
        }
    }