Не удалось получить сортировку вставкой из введения в алгоритмы, 3-е изд. правильно. В чем моя ошибка мышления?

Я работаю над книгой Введение в алгоритмы, 3-е издание. Одно из первых объяснений - это сортировка вставкой. На странице 18 есть некоторый псевдокод:

A = {5, 2, 4, 6, 1, 3};

INSERTION-SORT(A)
1 for j = 2 to A.length
2   key = A[j]
4   i = j - 1

5   while (i > 0 and A[i] > key)
6     A[i + 1] = A[i]
7     i = i - 1

8   A[i + 1] = key

Он говорит, что используется псевдокод, поэтому его легко переводить на любой язык ( C, C ++, Java, они не упоминают, но, наверное, и C # тоже). Поскольку я программирую на C #, я перевел его на LinqPad.

int[] a = { 5, 2, 4, 6, 1, 3 };

for (var j = 1; j < a.Length; j++)
{
    var key = a[j];

    var i = j - 1;

    while(i > 0 && a[i] > key)
    {
        a[i + 1] = a[i];
        i--;
    }

    a[i + 1] = key;
}

a.Dump();

Вы, наверное, спросите, почему j начинается с 1, когда явно написано 2? В книге массив имеет индекс, начинающийся с 1. И да, теперь мне, вероятно, следовало обновить все [i - 1] и [i + i] . .

В любом случае, когда я закончил, я запускаю код и замечаю, что он на самом деле сортируется неправильно. Результатом будет {5, 1, 2, 3, 4, 6} . Было поздно, и мне следовало остановиться, но я изо всех сил старался исправить код. Я все сделал, даже взял псевдокод как есть из книги (начиная с 2). По-прежнему неверный результат.

Я связался с одним из преподавателей книги, и он прислал мне код для сортировки вставкой на C:

void insertion_sort(int *A, int n) {
  for (int j = 2; j <= n; j++) {
    int key = A[j];
    int i = j-1;

    while (i > 0 && A[i] > key) {
      A[i+1] = A[i];
      i--;
    }

    A[i+1] = key;
  }
}

Переведено на C #:

int [] a = {5 , 2, 4, 6, 1, 3};

for (var j = 2; j <= a.Length; j++)
{
    var key = a[j];

    var i = j - 1;

    while(i > 0 && a[i] > key)
    {
        a[i + 1] = a[i];
        i--;
    }

    a[i + 1] = key;
}

Я получаю массив вне пределов. Хорошо, тогда может быть:

int [] a = {5, 2, 4, 6, 1, 3};

for (var j = 2; j <= a.Length - 1; j++)
{
    var key = a[j];

    var i = j - 1;

    while(i > 0 && a[i] > key)
    {
        a[i + 1] = a[i];
        i--;
    }

    a[i + 1] = key;
}

Вывод: {5, 1, 2, 3, 4, 6}

Я думаю, это не может быть правильно. Псевдокод сообщает array.Length 2. Это 2

Я лично думаю, что это из-за предиката 0> 0 в цикле while. На самом деле он каждый раз терпит неудачу один раз.

Мое объяснение (из моего электронного письма, отправленного профессору, ленивому набирать все заново):

Причина, по которой цикл все еще заканчивается на {5, 1, 2, 3, 4, 6} происходит из-за предиката i> 0 . Каждый раз в цикле while вы вычитаете 1 из i ( i - ). В конечном итоге это приведет к 0> 0 , что в конечном итоге окажется ложным (только 0 == 0 вернет истину), но это когда цикл все еще должен выполняться еще раз. Он постоянно терпит неудачу. Он должен выполнить цикл while еще 1 раз для правильной сортировки.

Другое объяснение:

Когда j начинается с 2, key == 4, i == 1 и a [i] == 2. Цикл while не будет работать в этом случае, потому что 2> 0, но 2 не больше 4.

j == 3, ключ == 6, я == 2, a [i] == 4

Цикл while не запускается, потому что 4 не больше 6

j == 4, ключ == 1, я == 3, a [i] == 6

На этот раз выполняется цикл while:

a [i + 1] = a [i] -> a [4] = a [3] -> {5, 2, 4, 6, 6, 3} i-- -> i == 2

Снова цикл while, потому что 2> 0 и 4> 1

a [i + 1] = a [i] -> a [3] = a [2] -> {5, 2, 4, 4, 6, 3} i - -> i == 1

Снова цикл while, потому что 1> 0 и 2> 1

a [i + 1] = a [i] -> a [2] = a [1] -> {5, 2, 2, 4, 6, 3} i-- -> i == 0

И вот здесь все идет (на мой взгляд) неправильно. i теперь равно нулю, но цикл while должен выполняться еще раз, чтобы вывести 5 из нулевой позиции.

Профессор уверяет меня, что он прав, но я не могу получить правильный результат. Где мои мысли ошибочны?

---

Массив в коде C, который мне прислал профессор, на самом деле начинался с индекса 1. Я этого не знал и проверяя массивы C, я увидел, что все они начинаются с 0. Да, тогда код C не дает правильного вывода. Профессор объяснил мне это, и теперь части встают на свои места.