Визуализация сортировки вставками

Что такое алгоритм сортировки вставками?

Сортировка вставками — это простой и эффективный алгоритм сортировки, который создает окончательный отсортированный массив (или список) по одному элементу за раз. Он гораздо менее эффективен для больших списков, чем более продвинутые алгоритмы, такие как быстрая сортировка, пирамидальная сортировка или сортировка слиянием, но он хорошо работает для небольших наборов данных или списков, которые уже частично отсортированы.

Implementations

Python

def insertion_sort(arr):
  for i in range(1, len(arr)):
    key = arr[i]
    j = i - 1
    while j >= 0 and key < arr[j]:
      arr[j + 1] = arr[j]
      j -= 1
    arr[j + 1] = key