You can try to avoid it by architecture or abstractions, but it only works to some extent.
Mind you this example is the one of the most trivial data structures in existence. Real software has insanely more complicated valid/invalid state, the size of the state space growing exponentially with the number of components.
And these are still single components, so the exponential growth of state combinations point is left unaddressed. In fact, it directly supersedes your point in this comment, as the exponentiality eats your "random data" idea before you even wrote it.
The way I look at testing is less about the current point in time. It is about changes over time. If someone else comes along and changes the underlying implementation to a list where sort order is not guaranteed (maybe thinking their version is faster or something), then the tests will fail and that's exactly what you want. You're testing the expected behavior over time and right now, the expected behavior is a sorted list.
Regardless, I don't understand what you're trying to argue or prove here. Yes, testing is hard and not easily won, I already said that.
I am arguing against your claim that this particular suggestion is feasible for anything but toy projects.
https://erikras.com/blog/final-form-to-typescript
"Of course, it helped that long ago I had put in all of the legwork to have near 100% test coverage, so I could be certain that the migration did not introduce any bugs."