I guess it depends on whether you want the records sorted in EEPROM or whether you just want to be able to sort them when they are output via serial comms.

If you do not need them sorted in EEPROM then I would just write them to EEPROM starting at the bottom of whatever block of EEPROM you use and write an index table which just consists of the addresses of the individual entries in sorted order at the top of the EEPROM block. This way you only need rewrite the index table when you make changes. (You will need to keep track of deletions so you can reclaim that space.)

If you need the records themselves to be sorted (faster lookup) then the simplest method is Insertion Sort where you move existing entries as needed to clear a slot for a new entry. This would be the worst case for EEPROM life.

I think it would be easier to learn VB. <img src="images/smilies/smile.gif" alt="" title="smile" class="inlineimg" border="0">