using System;
using System.Collections.Generic;
class Program
{
static void InsertionSort(List<int> arr)
{
int n = arr.Count;
for (int i = 1; i < n; ++i)
{
int key = arr[i];
int j = i - 1;
while (j >= 0 && key < arr[j])
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
static void Main()
{
List<int> arr1 = new List<int> { 1, 2, 3, 4, 5 };
InsertionSort(arr1);
foreach (int num in arr1)
{
Console.Write(num + " ");
}
Console.WriteLine();
List<int> arr2 = new List<int> { 5, 4, 3, 2, 1 };
InsertionSort(arr2);
foreach (int num in arr2)
{
Console.Write(num + " ");
}
Console.WriteLine();
List<int> arr3 = new List<int> { 2, 3, 1, 5, 4, 2 };
InsertionSort(arr3);
foreach (int num in arr3)
{
Console.Write(num + " ");
}
Console.WriteLine();
List<int> arr4 = new List<int> { 1 };
InsertionSort(arr4);
foreach (int num in arr4)
{
Console.Write(num + " ");
}
Console.WriteLine();
}
}