C#: best and worst case of insertion sort

Count comparisons on sorted, reversed, and mixed input to see how input order changes the cost.

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 }));
  }
}

Output

sorted input:   7
reversed input: 28
mixed input:    21

Explanation

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.

On input that is already sorted, every element stops after one comparison, so the total is n − 1. On reversed input, every element must pass all the elements before it, so the total is 1 + 2 + ... + (n − 1) = n(n − 1) / 2. Typical input falls between these two. The best case is linear and the worst case is quadratic.

Explore the dry run

Guided walkthroughReady

1using System;

3class Program {

4 static int Sort(int[] a) {

5 int comparisons = 0;

6 for (int i = 1; i < a.Length; i++) {

7 int key = a[i];

8 int j = i - 1;

9 while (j >= 0) {

10 comparisons++;

11 if (a[j] <= key) {

12 break;

13 }

14 a[j + 1] = a[j];

15 j--;

16 }

17 a[j + 1] = key;

18 }

19 return comparisons;

20 }

22 static void Main() {

23 Console.WriteLine("sorted input: " + Sort(new[] { 1, 2, 3, 4, 5, 6, 7, 8 }));

24 Console.WriteLine("reversed input: " + Sort(new[] { 8, 7, 6, 5, 4, 3, 2, 1 }));

25 Console.WriteLine("mixed input: " + Sort(new[] { 4, 8, 2, 7, 1, 6, 3, 5 }));

26 }

27}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Each pass of the inner loop compares the key with one earlier element.	`—`	—
As soon as an earlier element is not larger, the key is in place and the loop stops.	`—`	—
Sorted input: one comparison per element after the first, 7 in all.	`—`	sorted input: 7
Reversed input: 1 + 2 + ... + 7 = 28 comparisons, which is n(n−1)/2.	`—`	sorted input: 7 reversed input: 28
Mixed input falls between the extremes: 21 comparisons.	`—`	sorted input: 7 reversed input: 28 mixed input: 21

Cost and common mistakes

Best case Θ(n), worst case Θ(n²), O(1) extra space.

The bounds depend on the input order, not only its size. Always say which case a bound describes.
Insertion sort is quadratic in the worst case but very fast on nearly sorted data, which is why some library sorts use it for small ranges.

Try it yourself

How many comparisons does reversed input of 10 elements need?

Reveal answer and reasoning

10 · 9 / 2 = 45 comparisons.

C#: best and worst case of insertion sort

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading