Evidently so; I haven't changed that version of my_sort in my post. The resulting order is still a mess. However, like the OP, if I use sort { my_sort() } @data instead of sort my_sort @data, I get correct ordering. So whatever the problem is in using goto, it isn't fixed by using redo. I begin to smell a bug in perl (or something that could stand to be documented).

Printing $i each time it is assigned shows that when the sort sub is given by name, its value never decreases. When it is wrapped in a sub, it often goes back to zero. I think the problem is in auto-vivifying $_[0].