[yoden]

That's not what he's saying. He's saying the test should measure an externally visible detail. In this case that would be "is the list sorted". This way the test will still pass without maintenance if the sorting algorithm is switched again in the future. You can still consider the implementation to create antagonistic test cases.

[Beldin]

One of my colleagues helped find the Timsort bug and recently another such bug (might be the Java binary search, don't remember).

The edge case to show a straightforward version of that recent bug basically required a supercomputer. The artifact evaluation committee complained even.

So you can try to test for that only based on output. But it's gigantically more efficient to test with knowledge of internals.

[jeffffff]

this sounds like a case where no amount of unit testing ever would've found the bug. someone found the bug either through reasoning about the implementation or using formal methods and then wrote a test to demonstrate it. you could spend your entire life writing unit tests for this function and chances are you would never find out there was an issue. i'd say this is more of an argument for formal methods than it is for any approach to testing.

[Beldin]

But once you've found the bug, you'd like to add a test case that prevents regression - a test case that doesn't require a supercomputer.

That might not always be possible - but if it is, the test would be based on implementation details.