Sorting

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.

sorted prefix Positions before the scan index are already sorted.
shifting Larger values move one slot right to make room for the key.

Basic Implementation

basic.cs
Replay: real traced execution (multi-file project)
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("]");
	}
}

  1. arr ← [5, 1, 4, 2, 8]

    1using System;
    values this step[5, 1, 4, 2, 8]arr

  2. arr ← [1, 5, 4, 2, 8]

    6for (int i = 1; i < arr.Length; i++) {7	int key = arr[i];8	int j = i - 1;
    values this step[5, 1, 4, 2, 8] → [1, 5, 4, 2, 8]arr1key

  3. arr ← [1, 4, 5, 2, 8]

    8int j = i - 1;9while (j >= 0 && arr[j] > key) {10	arr[j + 1] = arr[j];
    values this step[1, 5, 4, 2, 8] → [1, 4, 5, 2, 8]arr4key

  4. arr ← [1, 2, 4, 5, 8]

    8int j = i - 1;9while (j >= 0 && arr[j] > key) {10	arr[j + 1] = arr[j];
    values this step[1, 4, 5, 2, 8] → [1, 2, 4, 5, 8]arr2key

  5. stdout ← [1, 2, 4, 5, 8]

    23	}24	Console.WriteLine("]");25}
    values this step[1, 2, 4, 5, 8]stdout[1, 2, 4, 5, 8]arr

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 Array.Sort. The replay is meant to expose each comparison, shift, and insertion point.
  • The int[] is a managed reference array; arr[j + 1] = arr[j] mutates the same object in place, and each indexed read/write is bounds-checked by the CLR while the j >= 0 guard keeps the left edge explicit.