Insertion sort is a simple sorting algorithm that builds the final sorted list one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

For more information about Insertion Sort Algorithm:
http://en.wikipedia.org/wiki/Insertion_sort

Implementation and Usage:

            int[] arr = new int[10]
            {
                1, 5, 4, 11, 20, 8, 2, 98, 90, 16
            };

            InsertionSort(arr);
            Console.WriteLine("Sorted Values:");
            for (int i = 0; i < arr.Length; i++)
                Console.WriteLine(arr[i]);

            //Output:
            //Sorted Values:
            //1
            //2
            //4
            //5
            //8
            //11
            //16
            //20
            //90
            //98

        private void InsertionSort(int[] arr)
        {
            int j, temp;
            for (int i = 1; i <= arr.Length - 1; i++)
            {
                temp = arr[i];
                j = i - 1;
                while (j >= 0 && arr[j] > temp)
                {
                    arr[j + 1] = arr[j];
                    j--;
                }
                arr[j + 1] = temp;
            }
        }

See Also:

• Selection Sort Algorithm
• Bubble Sort Algorithm
• Counting Sort Algorithm
• Quick Sort Algorithm
• Merge Sort Algorithm