You're in luck. If someone were asking me to sort strings, sort would be my second choice too. My first choice would probably be Unicode::Collate. Wrap your solution around that module, and you've satisfied the requirement of not using sort, while at the same time providing a better solution that sort would have offered in the first place.

I'm aware that this answer probably is of little help to you in your interview; the interviewer probably wants to see you write a sort. But if he's interested in getting the job done well, maybe he will respect the answer. ;)