Insertion Sort

Build the sorted prefix one item at a time, shifting larger values right until the current key can be inserted.

Algorithm

The checked-in replay follows the same small input and final output across all 21 DSA books, so this C# DSA implementation can be compared directly with the other languages.

Basic Implementation

basic.cs

using System;

class Program {
	static void Main() {
		int[] arr = new int[] { 5, 1, 4, 2, 8 };
		for (int i = 1; i < arr.Length; i++) {
			int key = arr[i];
			int j = i - 1;
			while (j >= 0 && arr[j] > key) {
				arr[j + 1] = arr[j];
				j--;
			}
			arr[j + 1] = key;
		}
		PrintArray(arr);
	}

	static void PrintArray(int[] arr) {
		Console.Write("[");
		for (int i = 0; i < arr.Length; i++) {
			if (i > 0) Console.Write(", ");
			Console.Write(arr[i]);
		}
		Console.WriteLine("]");
	}
}

Complexity

Time: O(n^2) worst and average, O(n) best
Space: O(1)
Stable: yes

Implementation notes

Keep the explicit algorithmic steps instead of calling a standard-library sort. The replay is meant to expose comparisons, movement, and recursion.
The implementation is intentionally compact for learning and replay, not a production sorting utility.

sorted prefix Positions before the scan index are already sorted.

shifting Larger values move one slot right to make room for the key.