Hi lpwevers
If you are allowed to install new libraries, how about trying to install and run the Sort::Naturally sort? I am not sure if it will make a difference, but it might be worth a try.
http://search.cpan.org/~bingos/Sort-Naturally-1.03/lib/Sort/Naturally.pm#The_nsort_function
Once installed , you just need to replace 'sort' with 'nsort' ( in addition to the use Sort::Naturally; line ).
I hope this helps.