sort() + parseInt() + innerText + appendChild().
А вообще, при вашей структуре html можете собирать все содержимое элементов, пихать его в массив, сортировать и генерировать новый html на замену старого.
Итак, вижу такие варианты:
1. Создавать и грузить записи по 1000. Операция одноразовая, так что не важно, сколько времени она займет.
2. Силами php создать файл sql и один раз загрузить его.
3. Создавать записи при первом запросе.
4. Накуривать запрос sql для генерации записей.
Выбирайте что вам понятнее. =)