Exactly. Nobody's on board with paying at least twice as much for software though. But that's what you get when things change and you have to refactor BOTH your code AND your tests.
I 100% agree with capturing requirements in tests. However, I argue that TDD does not cause that to happen.
I'd even make a stronger statement. Automated tests that don't capture a requirement should be deleted. Those sorts of tests only serve to hinder future refactoring.
A good test for a sort method is one that verifies data is sorted at the end of it. A bad test for a sort method is one that checks to see what order elements are visited in the sorting process. I have seen a lot of the "element order visit" style tests but not a whole lot of "did this method sort the data" style tests.
I don't see the connection between TDD and your bad tests examples though.
I would test a sort method just the way you describe, using TDD.
So, you say "Ok, I'll need a `heapify` method and a `siftDown` methods, so I'm going to write the tests to make sure both of those are working properly". But remember, we started this discussion saying "we need a sort method". So now, if you decide "You know what, heapsort is garbage, let's do tim sort instead!" Now, all the sudden you've got a bunch of useless tests. In the best case, you can simply delete those tests, but often devs often get intimidated deleting such tests "What if something else needs the `heapify` method"?
And that's exactly the problem I was pointing out with the example. We started the convo saying "tests couple implementation" and that's what's happened here. Our tests are making it seem like heap sort is the implementation we should use when we started this convo, we just needed a sorting method.
But now imagine we are talking about something way more complicated and/or less well known than a sorting algorithm. Now, it becomes a lot harder to sift out which tests are for implementation things and which are for requirements things. Without deleting the "these tests make sure I did a good implementation" future maintainers of the code are left to guess on what's a requirement and what's an implementation detail.
All sort methods can and should be tested with the same tests, that assert that unsorted input is converted to sorted output.
Choosing heapsort for performance reasons should normally not affect your test suite at all.
That's not to say you can't seek improvement. The public interface can be expanded without impacting existing uses. If, for example, an existing function doesn't reflect your current view of the world add a new one rather than try to jerry-rig the old one. If the new solutions are radically different such that you are essentially rewriting your code from scratch, a clean break is probably the better route to go.
If you are confident that existing users are no longer touching your legacy code, remove it rather than refactor it.
Things change. You change the code in response. What broke? Without the tests, you don't know.
"Things change" include "you fixed a bug". Bug fixes can create new bugs (the only study I am familiar with says 20-50% probability). Did your bug fix break anything else? How do you know? With good test coverage, you just run the tests. (Yes, the tests are never complete enough. They can be complete enough that they give fairly high confidence, and they can be complete enough to point out a surprising number of bugs.)
Does that make you pay "at least twice"? No. It makes you pay, yes, but you get a large amount of value back in terms of actually working code.
You aren't doing "double the work" even though it seems that way on paper, unless the problem was solved with brittle architectural foundations and tightly coupled tests.
At the heart of this problem is most developers don't quite grasp boundary separation intuitively I think.