волшебно

[thedeemon]

Некие люди занимались верификацией всякого кода на Джаве и столкнулись с трудностями при доказательстве корректности TimSort'a - алгоритма сортировки, издавна используемого в Питоне и Джаве. Оказалось, что он некорректен, на некоторых данных не работает вообще.

Proving that Android’s, Java’s and Python’s sorting algorithm is broken (and showing how to fix it)

Кому вообще нужны эти теорем-пруверы? Питон, тесты, махание руками!

Comments

[nivanych.livejournal.com]

Я ещё понимаю реакцию на "broken".
Но на
> (and showing how to fix it)
надо ж радоваться полчаса!

[thedeemon.livejournal.com]

Так правильное решение, вероятно, медленнее, потому джавщики предпочли просто размер буфера увеличить, авось проканает. Вон в питоне буфер побольше, там канает, хоть и ошибка в логике.

[nivanych.livejournal.com]

Эпично, эпично.
Надеюсь, расползётся и побольше народу узнает.
Например, средствами чОрного пеара —
"Воон там какие-то придурки со своей математикой припёрлись и чо оно получили? Малозначительную issue нашли. Всё бы им в своей ерунде ковыряться, а не работать!" ;-)
Можно гораздо красочнее расписать, если чуть постараться ;-)

[gegmopo4.livejournal.com]

Да, в предлагаемом решении на одно условие в цикле больше.