using System;

namespace Insertion_sort
{
	class MainClass
	{
		public static void Main(string[] args)
		{
			Random random = new Random();
			int[] insertionArray = new int[1000];

			// initialises the array
			for (int i = 0; i < insertionArray.Length; i++)
			{
				insertionArray[i] = random.Next(10000);
			}

			for (int i = 0; i < insertionArray.Length; i++)
			{
				Console.WriteLine(insertionArray[i]);
			}

			Console.WriteLine("-");

			int arrayLength = insertionArray.Length;
			int swapValue;

			for (int i = 0; i < insertionArray.Length; i++)
			{
				swapValue = insertionArray[i];
				for (int j = i; j > 0; j--)
				{
					if (insertionArray[j - 1] > swapValue)
					{
						if (j == 1)
						{
							insertionArray = ArrayInsertion(insertionArray, j - 1, i, swapValue);
							break;
						}
						else if (insertionArray[j - 2] <= swapValue)
						{
							insertionArray = ArrayInsertion(insertionArray, j - 1, i, swapValue);
							break;
						}
					}
				}
			}


			for (int i = 0; i < insertionArray.Length; i++)
			{
				Console.WriteLine(insertionArray[i]);
			}


		}
		public static int[] ArrayInsertion(int[] insertionArray, int indexToSwap, int indexSwapingFrom, int valueToBeInserted)
		{
			int[] tempArray = new int[indexSwapingFrom - indexToSwap];

			for (int k = 0; k < tempArray.Length; k++)
			{
				tempArray[k] = insertionArray[k + indexToSwap];
			}

			insertionArray[indexToSwap] = valueToBeInserted;

			for (int k = 0; k < tempArray.Length; k++)
			{
				insertionArray[k + indexToSwap + 1] = tempArray[k];
			}

			return insertionArray;
		}
	}
}