Remember that a stupid sort will not only take time. It will also result in a large wear on the memory. If you simulate your sorts on a PC, you can easily keep track of the number of writes to each memory record.

Another problem is what happens if you get a power failure while sorting? An embedded device would normally need to have a stable sort that duplicates entries before move so that the erase can be undone if the processor fails before writing the changed entry. Such logic will further increase the number of writes.

How many entries do you have? An alternative for you is to store indices to the entries in RAM. Then the full sort can be performed in RAM, with just a large number of reads into the I2C memory when doing the key-compare between two indexed entries. You could then potentially write back the sorted array into a second part for the EEPROM memory, with only one signel cycle of wear.

If the RAM isn't large enough for storing the full set of indices, then there are multi-pass sorts. You sort as many entries as you can in RAM, and save the indices of the sorted entries. Then you sort the next set of entries and sort in second output table.

When having run through all data like that, you then runs a second pass through the data. This time by picking up the first entry from each of the output tables. Compare them and emit the "first" entry. Get the next entry from that sub-table and continue to compare/emit until you have sorted/emitted the full set of data.

Using multipass sort, you can sort data that are any number of times larger than what your RAM can hold. And the sort will still be many, many, many times faster than trying to do a one-pass sort. And the wear on the EEPROM will be much, much lower too, since you will avoid all the swapping between two entries. The number of writes/entry may be two, instead of growing with the sqrt of n, where n is the total number of entries to sort.

Your best reference for sorting is the Donald E. Knuth book "Art of Computer Programming, Volume 3: Sorting and Searching". But the multipass sort is so simple that you can write it yourself (bubble-sort or insertion-sort is normally is ok for each partial patch) or look for some nice implementations using Google.