graff,
I have considered *nix utilities, but it requires more assumptions than just not having imbedded newlines. For instance, if the key field is the 3rd column, you need to sort by the 3rd column and not the first. CSV can get quite messy and even with the power of awk, it will likely have to be changed for each new type of CSV encountered.

Originally, I figured if I needed to pre-process the file anyway, I might as well just go ahead and do the sort in Perl. That could potentially be a "bad" idea given the size of these files is currently unknown (at least to me). I really like the idea of indexing information and sorting that rather than the whole file. I will give this some more thought and perhaps will come up with a hybrid.