Time and Space Complexity

Временная сложность:

• Лучший случай: O(n)
  • Когда массив уже отсортирован, сортировка вставками (Insertion Sort) делает только один проход, чтобы подтвердить порядок сортировки.
• Средний и худший случаи: O(n²)
  • В среднем и худшем случаях требуется квадратичное время, так как для каждого элемента может потребоваться сравнение и сдвиг через всю отсортированную часть.

Пространственная сложность:

• O(1)
  • Сортировка вставками — это алгоритм «на месте» (in-place), что означает, что он не требует дополнительной памяти, пропорциональной размеру входных данных.
  • Объем памяти, используемый для сортировки, остается постоянным независимо от размера входных данных.

Резюме:

• Сортировка вставками эффективна для небольших наборов данных или почти отсортированных массивов.
• Она менее пригодна для больших наборов данных из-за своей квадратичной временной сложности.
• Пространственная сложность постоянна, что делает алгоритм эффективным с точки зрения памяти для любого размера входных данных.