Insertion sort program in C#

Insertion sort is a simple sorting algorithm that builds the final sorted array one element at a time. It works by dividing the input array into two parts: the sorted part and the unsorted part. Initially, the sorted part contains only the first element, and the rest of the elements are considered part of the unsorted part.

The algorithm iterates through the unsorted part of the array, selecting one element at a time and inserting it into its correct position within the sorted part. To insert an element, it compares it with the elements in the sorted part, moving the larger elements one position to the right until it finds the correct position for the element.

using System;

public class InsertionSort
{
    public static void Main()
    {
        int[] arr = { 64, 25, 12, 22, 11 };

        Console.WriteLine("Original array:");
        PrintArray(arr);

        Sort(arr);

        Console.WriteLine("Sorted array:");
        PrintArray(arr);
    }

    public static void Sort(int[] arr)
    {
        int n = arr.Length;

        for (int i = 1; i < n; i++)
        {
            int key = arr[i];
            int j = i - 1;

            // Move elements of arr[0..i-1] that are greater than key, to one position ahead of their current position
            while (j >= 0 && arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j--;
            }

            arr[j + 1] = key;
        }
    }

    public static void PrintArray(int[] arr)
    {
        foreach (int num in arr)
        {
            Console.Write(num + " ");
        }
        Console.WriteLine();
    }
}

In this example, the Sort method implements the insertion sort algorithm. The Main method initializes an array, calls the Sort method to sort the array, and then prints both the original and sorted arrays using the PrintArray method.

Original array:
64 25 12 22 11 
Sorted array:
11 12 22 25 64 

The program demonstrates the step-by-step execution of the insertion sort algorithm on the given array and outputs the sorted array.

Insertion sort has a time complexity of O(n^2) in the worst case, where n is the number of elements in the array. However, it performs efficiently on small or partially sorted arrays.