Сортировка вставками, описанная в книге «Алгоритмы» Кормена и других авторов, работает следующим образом: она последовательно проходит по массиву, и для каждого элемента (начиная со второго) вставляет его в отсортированную часть массива (которая накапливается слева). Если у вас возникают трудности с неправильной работой сортировки, то это может быть вызвано несколькими причинами:
1. **Некорректная реализация**: Возможны ошибки в логике вставки элемента в отсортированную часть.
2. **Ошибки с индексами**: Неправильное управление индексами может привести к тому, что элементы будут сравниваться или сдвигаться неверно.
3. **Обработка одинаковых значений**: В случае одинаковых значений сортировка должна их корректно обрабатывать, чтобы сохранить их порядок (если алгоритм стабильный).
Вот псевдокод для сортировки вставками из книги «Алгоритмы»:
```plaintext
INSSORT(A)
1 for j = 2 to length(A) do
2 key = A[j]
3 // Вставляем A[j] в отсортированную часть
4 i = j - 1
5 while i > 0 and A[i] > key do
6 A[i + 1] = A[i]
7 i = i - 1
8 A[i + 1] = key
```
В этом псевдокоде `A` — это массив, который мы хотим отсортировать. На каждой итерации мы берем ключ `key` и сдвигаем все элементы, которые больше `key`, вправо, чтобы освободить место для вставки. Неправильная работа может происходить, если условие в строке 5 (или его аналог) реализовано неверно.
Если у вас есть конкретный код, который вы реализовали, вы можете поделиться им, и я постараюсь помочь вам найти возможные ошибки.