C#: best and worst case of insertion sort
Insertion sort builds a sorted prefix one element at a time. For each new element it moves left past every larger element until it finds the right place. The number of comparisons therefore depends on how far each element has to move.
C#
using System;
class Program {
static int Sort(int[] a) {
int comparisons = 0;
for (int i = 1; i < a.Length; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0) {
comparisons++;
if (a[j] <= key) {
break;
}
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
return comparisons;
}
static void Main() {
Console.WriteLine("sorted input: " + Sort(new[] { 1, 2, 3, 4, 5, 6, 7, 8 }));
Console.WriteLine("reversed input: " + Sort(new[] { 8, 7, 6, 5, 4, 3, 2, 1 }));
Console.WriteLine("mixed input: " + Sort(new[] { 4, 8, 2, 7, 1, 6, 3, 5 }));
}
}