Алгоритм сортировки вставками так же невозможно закончить «преждевременно», то есть тогда, когда на каком-то шаге мы видим, что массив уже отсортирован, но сам алгоритм еще не прошел все итерации. В мультфильме массив был отсортирован фактически на 1-ой итерации (мы увидели это глазами), но в теории мы не можем этого знать, так как не знаем ничего про оставшиеся элементы в неотсортированной части.