in reply to how to sort string in perl
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. ;)