СВ: /* Связанные темы */

2026-10-27T22:13:59Z

Связанные темы

← Предыдущая		Версия 22:13, 27 октября 2026
Строка 353:		Строка 353:
	== Связанные темы ==		== Связанные темы ==

	* [[Сортировки]] ~~(план)~~ — обзор алгоритмов и нижняя граница <math>\Omega(n\log n)</math>.		* [[Сортировки]] — обзор алгоритмов и нижняя граница <math>\Omega(n\log n)</math>.
	* [[Сортировка Шелла]] ~~(план)~~ — обобщение вставок на убывающие шаги.		* [[Сортировка Шелла]] — обобщение вставок на убывающие шаги.
	* [[Сортировка пузырьком]] — обменный родственник; вставки почти всегда его быстрее.		* [[Сортировка пузырьком]] — обменный родственник; вставки почти всегда его быстрее.
	* [[Быстрая сортировка]] ~~(план)~~ — introsort и переключение на вставки.		* [[Быстрая сортировка]] — introsort и переключение на вставки.
	* [[Сортировка слиянием]] ~~(план)~~ — гибрид с вставками на малых отрезках.		* [[Сортировка слиянием]] — гибрид с вставками на малых отрезках.
	* [[Timsort]] ~~(план)~~ — бинарные вставки для удлинения runs (minrun).		* [[Timsort]] — бинарные вставки для удлинения runs (minrun).
	* [[Пирамидальная сортировка]] ~~(план)~~ — другой <math>O(1)</math>-по-памяти алгоритм.		* [[Пирамидальная сортировка]] — другой <math>O(1)</math>-по-памяти алгоритм.
	* [[Асимптотическая сложность]] ~~(план)~~ — лучший/средний/худший случаи.		* [[Асимптотическая сложность]] — лучший/средний/худший случаи.

	== Источники ==		== Источники ==

СВ: Новая страница: «== TL;DR == '''Сортировка вставками''' (insertion sort) поддерживает '''отсортированный префикс''' масс...»

2026-09-30T19:21:06Z

Новая страница: «== TL;DR == '''Сортировка вставками''' (insertion sort) поддерживает '''отсортированный префикс''' масс...»

Новая страница

== TL;DR ==

'''Сортировка вставками''' (insertion sort) поддерживает '''отсортированный префикс''' массива и на каждом шаге вставляет в него очередной элемент, сдвигая бо́льшие элементы вправо. Алгоритм прост, работает '''на месте''' (<math>O(1)</math> памяти), '''устойчив''' и '''адаптивен''': почти отсортированный массив сортируется за <math>O(n)</math>. В худшем (обратный массив) и среднем случаях — <math>\Theta(n^2)</math>. Точная стоимость — <math>\Theta(n + \text{inv})</math>, где <math>\text{inv}</math> — число '''инверсий''': каждый сдвиг устраняет ровно одну инверсию. '''Бинарная''' версия ищет позицию двоичным поиском (<math>O(n\log n)</math> сравнений), но сдвиги остаются <math>O(n^2)</math>. Благодаря простоте и дешевизне на малых отрезках вставки служат '''базой гибридных сортировок''' — [[Быстрая сортировка\|introsort]], [[Сортировка слиянием\|mergesort]], [[Timsort\|Timsort]] (minrun) — переключаются на них при <math>n < 16\ldots32</math>.

{| class="wikitable"
|-
! Свойство !! Значение
|-
| Класс || Сортировка сравнением; на месте; устойчивая; онлайн
|-
| Лучший случай || <math>\Theta(n)</math> (уже отсортирован)
|-
| Средний случай || <math>\Theta(n^2)</math> (~<math>n^2/4</math> сравнений)
|-
| Худший случай || <math>\Theta(n^2)</math> (<math>n(n-1)/2</math> сравнений)
|-
| Перемещений || <math>\Theta(n + \text{inv})</math> (inv — число инверсий)
|-
| Память || <math>O(1)</math>
|-
| Устойчивость || да (строгое «>» при сдвиге)
|-
| Адаптивность || высокая (<math>O(n)</math> на почти отсортированных)
|-
| Бинарная версия || <math>O(n\log n)</math> сравнений, но <math>O(n^2)</math> перемещений
|-
| Роль || база гибридов; малые массивы; Shellsort
|-
| Родственники || [[Сортировки|обзор сортировок]], [[Timsort]], [[Сортировка слиянием]]
|}

== Определения ==

'''Сортировка вставками''' — алгоритм, который поочерёдно (слева направо) вставляет элемент <math>a[i]</math> в уже отсортированный отрезок <math>a[0..i-1]</math>, сдвигая элементы, большие <math>a[i]</math>, на одну позицию вправо, и кладёт <math>a[i]</math> на освободившееся место.

'''Отсортированный префикс''' — отрезок <math>a[0..i-1]</math>, который поддерживается неубывающим на каждом шаге. Полное отсортирование достигается при <math>i = n</math>.

'''Устойчивость (stability)''' — равные элементы сохраняют исходный порядок. Вставки устойчивы, потому что сдвигаются только элементы, '''строго большие''' вставляемого.

'''На месте (in-place)''' — используется <math>O(1)</math> дополнительной памяти (одна переменная под вставляемый элемент).

'''Онлайн-алгоритм''' — может сортировать данные по мере их поступления, имея отсортированными уже прочитанные элементы.

'''Инверсия''' — пара индексов <math>i < j</math> с <math>a[i] > a[j]</math>; мера «беспорядка». В сортировке вставками каждый сдвиг устраняет ровно одну инверсию.

'''Бинарная сортировка вставками''' — вариант, в котором позиция вставки ищется '''двоичным поиском''' за <math>O(\log i)</math>, но перемещение элементов всё равно выполняется сдвигом.

'''Shellsort''' — обобщение: сортировка вставками по подпоследовательностям с убывающими шагами; элементы перемещаются на большие расстояния, что ускоряет последующие проходы.

'''Обозначения.''' <math>n</math> — длина массива; <math>i</math> — текущий индекс; <math>\text{inv}</math> — число инверсий; <math>\log</math> — двоичный.

== Мотивация и интуиция ==

Сортировка вставками — вероятно, '''простейший''' алгоритм сортировки, и у него есть три свойства, делающие его незаменимым на практике: '''на месте''', '''устойчив''' и '''адаптивен'''. На массиве, где беспорядка мало (почти отсортированном, или «немного подправленном»), она обгоняет и quicksort, и mergesort, потому что делает работу, пропорциональную числу инверсий.

Идея в одном абзаце: '''держим префикс отсортированным'''. Вставляя <math>a[i]</math>, достаточно раздвинуть часть префикса, чтобы найти место; чем меньше инверсий у <math>a[i]</math>, тем меньше сдвигов. В пределе (массив уже отсортирован) каждый элемент вставляется на своё место за одно сравнение — суммарно <math>n-1</math>, то есть <math>O(n)</math>.

Именно поэтому вставки используют как '''«хвост»''' рекурсивных сортировок: на коротких отрезках рекурсия и накладные расходы дороже, чем прямая вставка; а почти отсортированные данные — частая реальность.

[[Файл:iv-01-idea.svg|frame|none|700px|Рис. 1. Вставляем элемент в отсортированный префикс, сдвигая большие элементы вправо.]]

[[Файл:iv-02-inversions.svg|frame|none|700px|Рис. 2. Сдвигов ровно столько, сколько инверсий: отсортированное — <math>O(n)</math>, обратное — <math>\Theta(n^2)</math>.]]

== Устройство ==

Два «указателя»: граница отсортированного префикса <math>i</math> и позиция <math>j</math> внутри префикса, идущая справа налево в поиске места. Вставляемый элемент сохраняется в переменной (это и есть дополнительная «память» <math>O(1)</math>), затем сдвигаются элементы.

* '''Массив.''' Сдвиг — это запись элементов на соседние позиции (<math>O(n)</math> в худшем); вставка дешёва по количеству обменов, но перемещения памяти могут быть дорогими.
* '''Связный список.''' Сдвиг заменяется обновлением указателей; но поиск места остаётся линейным, поэтому общая сложность всё равно <math>O(n^2)</math> (см. рис. 5).

[[Файл:iv-03-trace.svg|frame|none|700px|Рис. 3. Массив после каждого шага: префикс слева растёт и остаётся отсортированным.]]

== Операции и алгоритмы ==

=== Операция: Insertion-Sort (линейный поиск места) ===

'''Идея.''' Для каждого <math>i</math> «протаскиваем» <math>a[i]</math> влево, пока предыдущий элемент больше.

'''Пошаговое описание:'''

# Для <math>i</math> от <math>1</math> до <math>n-1</math>: сохранить <code>v ← a[i]</code>, <code>j ← i-1</code>.
# Пока <code>j ≥ 0</code> и <code>a[j] > v</code>: сдвинуть <code>a[j]</code> вправо (<code>a[j+1] ← a[j]</code>), <code>j ← j-1</code>.
# Положить <code>a[j+1] ← v</code>.

'''Инвариант.''' Перед обработкой <math>a[i]</math> отрезок <math>a[0..i-1]</math> отсортирован; элементы <math>a[i..n-1]</math> ещё не тронуты.

<syntaxhighlight lang="text">
Алгоритм Insertion-Sort(a)
Вход: массив a[0..n−1]
Выход: a отсортирован по неубыванию
Инвариант: перед шагом i отрезок a[0..i−1] отсортирован
Сложность: O(n + inv) перемещений; сравнений от n−1 (лучший) до n(n−1)/2 (худший)

1 for i ← 1 to n − 1
2 v ← a[i]
3 j ← i − 1
4 while j ≥ 0 and a[j] > v # строгое > → устойчивость
5 a[j + 1] ← a[j]
6 j ← j − 1
7 a[j + 1] ← v
</syntaxhighlight>

'''Разбор.''' <code>[5,2,4,6,1,3]</code> (см. рис. 3): после шагов получаем <code>[2,4,5,6|1,3]</code> → <code>[1,2,4,5,6|3]</code> → <code>[1,2,3,4,5,6]</code>; всего 9 сдвигов = число инверсий.

'''Сложность.''' Лучший <math>\Theta(n)</math>, средний <math>\Theta(n^2)</math>, худший <math>\Theta(n^2)</math>; память <math>O(1)</math>.

'''Крайние случаи.''' Отсортированный массив — <math>n-1</math> сравнение и 0 сдвигов. Обратный — <math>n(n-1)/2</math> сравнений и сдвигов. <math>n \le 1</math> — ничего.

=== Операция: Binary-Insertion-Sort ===

'''Идея.''' Позицию вставки искать двоичным поиском в отсортированном префиксе (см. рис. 4).

<syntaxhighlight lang="text">
Алгоритм Binary-Insertion-Sort(a)
Вход: массив a[0..n−1]
Выход: a отсортирован
Сложность: O(n log n) сравнений, но O(n²) перемещений ⇒ O(n²) времени

1 for i ← 1 to n − 1
2 v ← a[i]
3 lo ← 0 ; hi ← i # верхняя граница: первый p, где v < a[p]
4 while lo < hi
5 mid ← lo + ⌊(hi − lo) / 2⌋
6 if v < a[mid]: hi ← mid else lo ← mid + 1
7 for j ← i downto lo + 1
8 a[j] ← a[j − 1] # сдвиг
9 a[lo] ← v
</syntaxhighlight>

'''Разбор.''' На рис. 4 для <code>v = 4</code> позиция находится за 2–3 сравнения вместо 3–4.

'''Сложность.''' Сравнений <math>O(n\log n)</math>; перемещений по-прежнему <math>O(n^2)</math> → суммарно <math>O(n^2)</math>.

'''Крайние случаи.''' Двоичный поиск ищет '''верхнюю''' границу — равные не переставляются, код устойчив.

[[Файл:iv-04-binary.svg|frame|none|700px|Рис. 4. Меньше сравнений, но сдвиги те же: <math>O(n^2)</math> по перемещениям сохраняется.]]

=== Операция: сортировка вставками на списке ===

'''Идея.''' Идём по списку; каждый очередной узел вставляем в отсортированную часть, меняя указатели.

<syntaxhighlight lang="text">
Алгоритм List-Insertion-Sort(head)
Вход: односвязный список
Выход: отсортированный список
Сложность: O(n²) сравнений; перемещений — O(1) на вставку

1 sorted ← NIL
2 for each узел cur в исходном порядке
3 next ← cur.next
4 вставить cur в sorted на нужное место (линейный поиск)
</syntaxhighlight>

'''Крайние случаи.''' Вставка в начало; дубликаты (вставляем после равных — устойчиво).

[[Файл:iv-05-linkedlist.svg|frame|none|700px|Рис. 5. На списке вставка — обновление указателей, но поиск места линейный.]]

== Сводная таблица сложности ==

{| class="wikitable"
|-
! Операция !! Лучший !! Средний !! Худший !! Память
|-
| Сравнения || <math>n-1</math> || <math>\approx n^2/4</math> || <math>n(n-1)/2</math> || —
|-
| Перемещения (сдвиги) || <math>0</math> || <math>\approx n^2/4</math> || <math>n(n-1)/2</math> || —
|-
| Всего || <math>\Theta(n)</math> || <math>\Theta(n^2)</math> || <math>\Theta(n^2)</math> || <math>O(1)</math>
|-
| Binary-Insertion: сравнения || <math>O(n\log n)</math> || <math>O(n\log n)</math> || <math>O(n\log n)</math> || <math>O(1)</math>
|-
| Binary-Insertion: перемещения || <math>0</math> || <math>\Theta(n^2)</math> || <math>\Theta(n^2)</math> || <math>O(1)</math>
|-
| Точная формула || — || — || <math>\Theta(n + \text{inv})</math> || —
|}

Оговорка: точная оценка <math>\Theta(n+\text{inv})</math> показывает '''адаптивность''': при малом числе инверсий вставки линейны и обгоняют «быстрые» сортировки. На списке обменов <math>O(1)</math>, но сравнений <math>O(n^2)</math>.

== Трассировка примера ==

<code>a = [5, 2, 4, 6, 1, 3]</code> (см. рис. 3).

{| class="wikitable"
|-
! <math>i</math> !! Вставляем !! Действие !! Массив !! Сдвиги
|-
| 1 || 2 || 2 перед 5 || <code>[2, 5, 4, 6, 1, 3]</code> || 1
|-
| 2 || 4 || между 2 и 5 || <code>[2, 4, 5, 6, 1, 3]</code> || 1
|-
| 3 || 6 || на месте || <code>[2, 4, 5, 6, 1, 3]</code> || 0
|-
| 4 || 1 || в начало || <code>[1, 2, 4, 5, 6, 3]</code> || 4
|-
| 5 || 3 || между 2 и 4 || <code>[1, 2, 3, 4, 5, 6]</code> || 3
|}

Всего сдвигов: <math>1+1+0+4+3 = 9</math> — ровно число инверсий массива <code>[5,2,4,6,1,3]</code>. Трассировка сверена с реализацией из раздела «Служебное».

== Корректность и оценка сложности ==

=== Корректность (инвариант) ===

'''Инвариант цикла.''' Перед обработкой <math>a[i]</math> массив <math>a[0..i-1]</math> отсортирован; элементы <math>a[i..n-1]</math> не тронуты.

'''База.''' <math>i = 1</math>: префикс из одного элемента <math>a[0]</math> отсортирован.

'''Сохранение.''' При вставке <math>v = a[i]</math> мы находим первую справа позицию, где <code>a[j] ≤ v</code>, сдвигая строго большие элементы вправо. После этого <math>a[j+1] = v</math>, и префикс <math>a[0..i]</math> неубывающий: элементы слева <math>\le v</math> (по построению), справа были <math>> v</math> и сдвинуты. Инвариант сохранён.

'''Завершение.''' При <math>i = n-1</math> (после вставки) весь массив отсортирован. <math>\square</math>

=== Устойчивость ===

Сдвигаются только элементы со строгим <code>a[j] > v</code>; равные остаются слева от <math>v</math> и не меняют взаимного порядка. Значит, алгоритм устойчив.

=== Точная стоимость ===

Каждый сдвиг переносит больший элемент через меньший, устраняя ровно одну инверсию; обратные операции инверсий не создают. Значит, число сдвигов равно <math>\text{inv}(a)</math> — числу инверсий исходного массива. К этому добавляется по одной записи <math>v</math> на элемент, то есть

<math display="block">\text{перемещений} = \text{inv}(a) + (n - 1), \qquad \text{сравнений} \le \text{inv}(a) + (n-1).</math>

Отсюда: уже отсортированный массив — <math>O(n)</math>, обратный — <math>\Theta(n^2)</math>.

=== Бинарная версия ===

Позиция ищется за <math>\lceil\log_2 i\rceil</math> сравнений, суммарно <math>O(n\log n)</math>. Но сдвиг остаётся <math>\Theta(i)</math> в худшем, поэтому по времени алгоритм всё ещё <math>O(n^2)</math>; выигрыш — только в числе сравнений (важен при дорогом сравнении ключей).

== Сравнение с альтернативами ==

{| class="wikitable"
|-
! Алгоритм !! Средний !! Лучший !! Устойчив !! Память !! Ниша
|-
| '''Вставками''' || <math>O(n^2)</math> || <math>O(n)</math> || да || <math>O(1)</math> || малые, почти отсортированные
|-
| Выбором || <math>O(n^2)</math> || <math>O(n^2)</math> || нет || <math>O(1)</math> || мало обменов; вставки обычно лучше
|-
| Пузырьком || <math>O(n^2)</math> || <math>O(n)</math> || да || <math>O(1)</math> || учебный; вставки эффективнее
|-
| Слиянием || <math>O(n\log n)</math> || <math>O(n\log n)</math> || да || <math>O(n)</math> || большие <math>n</math>, списки
|-
| Быстрая || <math>O(n\log n)</math> || <math>O(n\log n)</math> || нет || <math>O(\log n)</math> || большие <math>n</math>, средняя скорость
|-
| Timsort || <math>O(n\log n)</math> || <math>O(n)</math> || да || <math>O(n)</math> || реальные данные
|}

[[Файл:iv-06-compare.svg|frame|none|700px|Рис. 6. Вставки проигрывают по асимптотике, но выигрывают на малых и почти отсортированных данных; отсюда — роль базы гибридов.]]

'''Вердикт.''' Для больших случайных массивов вставки не годятся (<math>O(n^2)</math>). Их ниша — '''короткие отрезки''' (внутри гибридов) и '''почти отсортированные''' данные. Именно поэтому introsort, mergesort и Timsort используют вставки как «хвост» рекурсии.

== Где применяется ==

# '''База гибридных сортировок.''' introsort (<code>std::sort</code>), mergesort, Timsort переключаются на вставки на коротких отрезках (порог 16–32). Почему: рекурсия и накладные расходы на малых отрезках дороже прямой вставки [1][4][6].

# '''Timsort и minrun.''' Timsort удлиняет короткие серии до minrun '''бинарными вставками''' — прямое использование варианта из этой статьи [5].

# '''Почти отсортированные данные.''' Обновлённые таблицы, инкрементальные вычисления, «подправленные» списки: стоимость <math>\Theta(n+\text{inv})</math> делает вставки самыми быстрыми [1][3].

# '''Онлайн-вставка.''' Поддержание отсортированного порядка при потоке элементов; на связном списке вставка = обновление указателей [3].

# '''Shellsort.''' Вставки на подпоследовательностях с убывающими шагами — практичный <math>O(n^{1.3})</math>–<math>O(n^{1.5})</math> алгоритм на средних массивах [2][3].

[[Файл:iv-07-applications.svg|frame|none|700px|Рис. 7. Вставки как база гибридов и для малых/почти отсортированных данных.]]

== Историческая справка ==

Сортировка вставками — одна из '''древнейших''' известных сортировок; её описывал ещё '''Джон Мокли''' (John Mauchly) в 1946 году, а систематический анализ дал '''Дональд Кнут''' в ''The Art of Computer Programming'', т. 3 (раздел 5.2.1): там же разобраны бинарный вариант, среднее число сравнений <math>\approx n^2/4</math> и связь с инверсиями [2]. Простота и адаптивность обеспечили ей место в учебниках как первого алгоритма сортировки (CLRS, гл. 2) [1].

'''Дональд Шелл''' в 1959 году обобщил вставки на подпоследовательности с убывающим шагом — '''Shellsort''', заметно ускорив алгоритм при малых накладных расходах [2][7]. Бинарный вариант (поиск позиции делением пополам) известен как '''binary insertion sort'''. В современных библиотеках вставки живут как «хвост» introsort/Timsort, где работают на коротких отрезках [4][5][6].

== Типичные ошибки и подводные камни ==

* '''Non-strict сравнение.''' <code>a[j] >= v</code> при сдвиге нарушает устойчивость; нужно строгое <code>></code>.
* '''Ошибка границ.''' <code>j ≥ 0</code> обязательно, иначе выход за массив при вставке в начало.
* '''Не сохранить <code>v</code>.''' Если не держать вставляемый элемент в переменной, его перезапишет сдвиг.
* '''Ожидание <math>O(n\log n)</math> от бинарной версии.''' Сравнений меньше, но перемещения остаются <math>O(n^2)</math>.
* '''Применение к большим случайным массивам.''' <math>O(n^2)</math> катастрофичен; для больших <math>n</math> — гибриды.
* '''Дорогие перемещения.''' Сдвиг больших структур (не чисел) медленный — либо список, либо обмен.
* '''Список вместо массива без нужды.''' На списке вставка дешевле по указателям, но кэш хуже; часто массив быстрее на практике.
* '''Забыть про адаптивность.''' На почти отсортированных данных вставки могут обогнать quicksort — не сбрасывайте их со счетов в гибридах.
* '''Путаница с сортировкой выбором.''' Выбором не адаптивна и неустойчива; вставки обычно выигрывают.
* '''Худший вход.''' Обратный массив — <math>\Theta(n^2)</math>; в гибридах от него спасает порог и переход на другой алгоритм.

== Задачи для практики ==

# '''Базовая реализация.''' Реализуйте сортировку вставками и посчитайте сравнения/сдвиги. ''Подсказка:'' инвариант — отсортированный префикс.

# '''Инверсии.''' Докажите, что число сдвигов равно числу инверсий; проверьте на примере. ''Подсказка:'' каждый сдвиг устраняет ровно одну инверсию.

# '''Лучший/худший.''' Для <math>n = 1000</math> найдите точные числа сравнений на отсортированном и обратном массивах. ''Подсказка:'' <math>n-1</math> и <math>n(n-1)/2</math>.

# '''Бинарная версия.''' Реализуйте binary insertion sort; сравните число сравнений с обычной. ''Подсказка:'' верхняя граница для устойчивости.

# '''Список.''' Отсортируйте односвязный список вставками; оцените сравнения и обновления указателей. ''Подсказка:'' вставка между узлами.

# '''Порог гибрида.''' Quicksort + вставки при <math>n < k</math>: подберите <math>k</math> по бенчмарку. ''Подсказка:'' 16–32.

# '''Почти отсортировано.''' Дан массив, где <math>k</math> элементов не на месте; оцените время вставок через инверсии. ''Подсказка:'' <math>\Theta(n + \text{inv})</math>.

# '''Shellsort.''' Реализуйте Shellsort с шагами Хиббарда и сравните с обычными вставками. ''Подсказка:'' вставки по подпоследовательностям.

== Связанные темы ==

* [[Сортировки]] — обзор алгоритмов и нижняя граница <math>\Omega(n\log n)</math>.
* [[Сортировка Шелла]] — обобщение вставок на убывающие шаги.
* [[Сортировка пузырьком]] — обменный родственник; вставки почти всегда его быстрее.
* [[Быстрая сортировка]] — introsort и переключение на вставки.
* [[Сортировка слиянием]] — гибрид с вставками на малых отрезках.
* [[Timsort]] — бинарные вставки для удлинения runs (minrun).
* [[Пирамидальная сортировка]] — другой <math>O(1)</math>-по-памяти алгоритм.
* [[Асимптотическая сложность]] — лучший/средний/худший случаи.

== Источники ==

# Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. ''Introduction to Algorithms'' (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 2.1 «Insertion sort» (инвариант, анализ).
# Knuth D. E. ''The Art of Computer Programming''. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §5.2.1 (insertion sort), §5.2.1 (Shellsort).
# Sedgewick R., Wayne K. ''Algorithms''. 4th ed. — Addison-Wesley, 2011. — §2.1 (Elementary Sorts).
# Musser D. R. Introspective Sorting and Selection Algorithms // Software: Practice and Experience. — 1997 (переключение на вставки в introsort).
# Peters T. listsort.txt (Timsort, бинарные вставки) URL: https://github.com/python/cpython/blob/main/Objects/listsort.txt .
# Wikipedia: Insertion sort. URL: https://en.wikipedia.org/wiki/Insertion_sort .
# Shell D. L. A High-Speed Sorting Procedure // CACM. — 1959. — Vol. 2, № 7 .

[[Category:Сортировки]]

Сортировка вставками - История изменений

СВ: /* Связанные темы */

СВ в 15:40, 26 октября 2026

СВ: Новая страница: «== TL;DR == '''Сортировка вставками''' (insertion sort) поддерживает '''отсортированный префикс''' масс...»