Forget that you, a human, thinks you know what an ISorter should do. What do the tests demand that you do?
Doing TDD, the goal, when coding, is to write the minimal amount of broken code that makes the test pass. If you passed me {4,3,2,1}, then my code would be "return {1,2,3,4};". If you wrote a second test that passed me {6,5,4,3}, my code would be "return (input[0]==4)?{1,2,3,4}:{3,4,5,6};". You've got to write a test that makes me actually code what you want. I use this adversarial approach even when I'm writing both the test and the code.
Usually the first test I write if I'm starting with a blank slate, is to pass null and check that I get a NullPointerException. That gets the class created. After that, its got to be randomly generated data.
What happens if you're implementing something like a unification algorithm, but you don't know about the occurs check. You'll progressively add test cases that break your code and eventually stop. Until an end user creates a query that contains itself and your algorithm fails to terminate.
The solution to get TDD to work is to know what all of the weird edge cases of your algorithm are. However, I assert that the thing that makes TDD ever work is that the practitioners who are "doing it right" already know all of the weird edge cases of their algorithms. And I assert that if you know the weird edge cases you can drop the test first part of TDD and still get working algorithms.
Random data is interesting because it's not something I've seen anyone mention when they talk about how they do TDD before now. I suppose if you knew nothing about your problem and had some sort of tool progressively feed you intelligently generated random data, that might work for algorithms that have few edge cases or relatively simple edge cases. However, it seems like you would want something more like quick check for cases where you have really esoteric edge cases. And I don't see how you avoid implementing bubble sort (or its equivalent in your domain).
I don't think TDD can't work, but so far nobody has described TDD to me where I have any reason to assume that TDD is actually doing anything worthwhile. It's always sounded like TDD was irrelevant and the real key to success was thinking about the problem carefully. Additionally, it sounds like there are problem domains where anything that TDD might bring to the table would be nullified (ie certain problems that exhibit a certain level of complexity).
So you're in a local maximum, and to get to the next, higher, maximum, you're going to have to go through a trough.
That being said, if anyone wants to fund me for six months (plus either some compensation to my employer for having me gone for six months OR a significant bonus for my own financial security) to try TDD, then I'll gladly do it.
That being said, I plan on putting it through one heck of a trail. At the end I'll either have a pretty good idea of exactly why TDD works OR I'll have a compelling argument for why it's gains are illusory.
For example,
This test will fail if you run it before the ISorter is implemented. But then it will pass if you implement an empty ISorter because the test still has problems (ie it starts with sorted input).Cue the ever familiar: You still have to use your brain when using TDD.
If TDD needs brain usage to function, maybe the real thing that is useful is the brain usage and TDD is vestigial.