3 ms·
> You would test a few values and edge cases until you were confident it works for all lists. However, you can't be 100% sure that there's some list out there l
by Izkata 7y ago
> You would test a few values and edge cases until you were confident it works for all lists. However, you can't be 100% sure that there's some list out there like [5,5,5,5,1] that doesn't get sorted properly.
For the curious, something like this has happened before - and was found with formal verification: http://www.envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/ http://www.envisage-project.eu/proving-android-java-and-pyth...