Void Swap(T[] items, int left, int right)

Сортировка вставками

Сложность	Наилучший случай	В среднем	Наихудший случай
Время	O(n)	O(n^2)	O(n^2)
Память	O(1)	O(1)	O(1)

Сортировка вставками работает, проходя по массиву и перемещая нужное значение в начало массива. После того, как обработана очередная позиция, мы знаем, что все позиции до нее отсортированы, а после нее — нет.
Важный момент: сортировка вставками обрабатывает элементы массива по порядку. Поскольку алгоритм проходит по элементам слева направо, мы знаем, что все, что слева от текущего индекса — уже отсортировано. На этом рисунке показано, как увеличивается отсортированная часть массива с каждым проходом:

Постепенно отсортированная часть массива растет, и, в конце концов, массив окажется упорядоченным.
Давайте взглянем на конкретный пример. Вот наш неотсортированный массив, который мы будем использовать:

Алгоритм начинает работу с индекса 0 и значения 3. Поскольку это первый индекс, массив до него включительно считается отсортированным.
Далее мы переходим к числу 7. Поскольку 7 больше, чем любое значение в отсортированной части, мы переходим к следующему элементу.
На этом этапе элементы с индексами 0..1 отсортированы, а про элементы с индексами 2..n ничего не известно.
Следующим проверяется значение 4. Так как оно меньше семи, мы должны перенести его на правильную позицию в отсортированную часть массива. Остается вопрос: как ее определить? Это осуществляется методом FindInsertionIndex. Он сравнивает переданное ему значение (4) с каждым значением в отсортированной части, пока не найдет место для вставки.
Итак, мы нашли индекс 1 (между значениями 3 и 7). Метод Insert осуществляет вставку, удаляя вставляемое значение из массива и сдвигая все значения, начиная с индекса для вставки, вправо. Теперь массив выглядит так:

Теперь часть массива, начиная от нулевого элемента и заканчивая элементом с индексом 2, отсортирована. Следующий проход начинается с индекса 3 и значения 4. По мере работы алгоритма мы продолжаем делать такие вставки.

Когда больше нет возможностей для вставок, массив считается полностью отсортированным, и работа алгоритма закончена.
public void Sort(T[] items)
{
int sortedRangeEndIndex = 1;

while (sortedRangeEndIndex < items.Length)

{
if (items[sortedRangeEndIndex].CompareTo(items[sortedRangeEndIndex - 1]) < 0)
{
int insertIndex = FindInsertionIndex(items, items[sortedRangeEndIndex]);
Insert(items, insertIndex, sortedRangeEndIndex);
}

sortedRangeEndIndex++;

}
}

private int FindInsertionIndex(T[] items, T valueToInsert)

{
for (int index = 0; index < items.Length; index++) {
if (items[index].CompareTo(valueToInsert) > 0)
{
return index;
}
}

throw new InvalidOperationException("The insertion index was not found");

}

private void Insert(T[] itemArray, int indexInsertingAt, int indexInsertingFrom)

{
// itemArray = 0 1 2 4 5 6 3 7
// insertingAt = 3
// insertingFrom = 6
//
// Действия:
// 1: Сохранить текущий индекс в temp
// 2: Заменить indexInsertingAt на indexInsertingFrom
// 3: Заменить indexInsertingAt на indexInsertingFrom в позиции +1
// Сдвинуть элементы влево на один.
// 4: Записать temp на позицию в массиве + 1.
// Шаг 1.
T temp = itemArray[indexInsertingAt];

// Шаг 2.

itemArray[indexInsertingAt] = itemArray[indexInsertingFrom];

// Шаг 3.

for (int current = indexInsertingFrom; current > indexInsertingAt; current--)
{
itemArray[current] = itemArray[current - 1];
}

// Шаг 4.

itemArray[indexInsertingAt + 1] = temp;
}