And the only way to fix it without generics is with a VM.
It's basically the same as what a JIT compiler does around type inference. If it can reason about the underlying type that's really going to Sort(), it can code generate a specialized version. The machinery for escape analysis that Go already has probably gets you at least part of the way there.
That pretty much boils down to a non-user-controllable templating done entirely through the compiler. Like I said... possible vs desirable.