А в JS же есть сортировка у массивов.
Или велосипедоизобретательств ом занимаетесь или я чего-то не понял? =/

Snipe,
Так у массивов же, а тут DOMNodeList.

Не писать же функцию сортировки вручную :D – есть же Array.sort. Его и помучаем:

var ul = document.getElementById("ul-1");
var lis = ul.getElementsByTagName("li"), li, h;
var map = {}, arr = [];
for(var i = 0, len = lis.length; i < len; i++) {
    li = lis[i];
    h = li.textContent || li.innerText; // превед, IE!
    if(!map[h]) // на случай повторяющихся значений h
        map[h] = [li]; // соответствие h => li
    else
        map[h].push(li);
    arr.push(h);
}
arr.sort(); // сортируем массив из h
if(ul._reverse)
	arr.reverse();
ul._reverse = !ul._reverse;
for(var i = 0; i < len; i++) // arr[i] => h => map[h] => li
    ul.appendChild(map[arr[i]].shift());

P.S. Старые версии IE будут нехило ругаться...