best way to sort and display a listing...

i am building a site game site(http://ultima-online.virtualave.net/cgi-bin/uo.pl) which allows players to enter information about themselves and their characters. The listing data is stored in a tab-delimeted file as "character_name\tshard\tuser_name\tdate_added". Visitors to the site are allowed to sort the list by character name, shard, username, or most recently added. Right now i simply have a sperate subroutine to sort and display the listings for each sort option.
The problem is this, i made a mock listing file of 500 records to see how long it would take to sort and display, and it took waaay tooo long, over a minute. So what im asking is this...

is there a better way to sort a large delimmeted text file?

one alternative i had is this...
keep 4 seperate listing data files, one for each method they could be sorted. When someone ADDS or UPDATES one of the files, fork 3 extra processes and have each process sort and rewrite a file. Then when the uo.pl script is called to display the listings, it would not need to sort anything, simply read the correct data file and display the contents.

Now, this would cause longer waits when someone updates the files, the files are updated a lot less than they are displayed, so i think it would be justified.
Does this make sense? Do i have the right idea? any suggestions?

see the script in its current state <a href="http://ultima-online.virtualave.net/non-cgi/source/uo.txt">here</a>.