Изменения
→Некорректность timsort в Java
На втором шаге,в последней тройке устанавливается инвариант и <tex>\mathtt{mergeCollapse}</tex> завершает свою работу, но инвариант для всего массива не восстановлен: он нарушается в первой тройке, так как <tex>23 < 16 + 9</tex>.
В результате нарушения инварианта, длины серий растут медленнее, чем ожидалось, в результате чего их кол-во превышает <tex>\mathtt{runLen.Length}</tex>, что привод приводит к <tex>\mathtt{ArrayOutOfBoundsException}</tex>.
Основная идея исправления ошибки {{---}} проверять, что инвариант соблюдается для четырёх последних серий в runLen вместо трёх.
}
}
== Источники информации==
