Алгоритм 1.
  1. Все TR удалить из таблицы, при этом собрав их в JavaScript-массив.
  2. Отсортировать этот массив, используя свою функцию в sort(...) для сравнения TR
  3. Добавить TR из массива в таблицу в нужном порядке
Алгоритм 2.
  1. Скопировать TR в JavaScript-массив.
  2. Отсортировать этот массив, используя свою функцию в sort(...) для сравнения TR
  3. Добавить TR из массива в таблицу в нужном порядке. При добавлении каждый TR сам удалится с предыдущего места.
Алгоритм 3.
  1. Создать массив из объектов вида {elem: ссылка на TR, value: содержимое TR}.
  2. Отсортировать массив по value. Функция сравнения во время сортировки теперь будет обращаться не к innerHTML, а к свойству объекта, это быстрее. Сортировка может потребовать многократных сравнений одного и того же элемента, отсюда выигрыш.
  3. Добавить TR в таблицу в нужном порядке (автоудалятся с предыдущего места).
Алгоритм 4.
  1. Выполнить алгоритм 3, но перед этим удалить таблицу из документа, а после - вставить обратно.
Алгоритм 5.
  1. Замерить время генерации таблицы (создаётся строка и пишется в innerHTML).

Содержимое документа для придания "реалистичности"

01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789