i remembered sonething: the apt packages are read into memory in order to sort them alphabetically, aren't they? (i.e. there's no database per se)
that being the case, then, well, doing a hierarchical office paperwork sort would do the trick. first not-sort by appending all packages beginning with a, then b etc and split out liba libb as well (this is not new, it's what debian archives do). then re-open and re-read and sort those individually. finally concatenate them together. this would literally reduce memory consumption by a factor of 50, removing all need for compromises. it also provides opportunities for speeding up sort time by allocating multiple processes to different starting letters. l. -- --- crowd-funded eco-conscious hardware: https://www.crowdsupply.com/eoma68