Fastest way to sort an unordered list's li elements / child nodes

I have a set of two lists with buttons to move items to and from each list.  The element tree for each list looks like this:

<div>
  <ul>
    <li>
      <label><input checkbox></label>
    </li>
  </ul>
</div>

My method for moving the elements works fine, but the problem is I also need to sort them after each transfer (The contents are strings).

Currently I do this by copying the UL's childNodes into a new array, sorting that array, deleting all nodes from the UL's childnodes, and copying the new ones in from the sorted clone array.  This gets really slow with high numbers of elements (around 1000).

Basically I'd like suggestions or links to better algorithms for doing this.

Here's my sorting code, performed after items are transferred from one list to the other.  dstObj is the UL that items were transferred to.

                var x = new Array();
      for(var j = 0; j < dstObj.childNodes.length; j++)
      {
           x[x.length] = dstObj.childNodes[j];
      }
      x.sort(itemOrder);
      
      while(dstObj.childNodes.length > 0) dstObj.removeChild(dstObj.childNodes[0]);
      
      for(var k = 0; k < x.length; k++)
      {
            dstObj.appendChild(x[k]);      
      }

      function itemOrder(a, b)     //Sort function,
      {
           var aUp = a.innerText.toUpperCase();
           var bUp = b.innerText.toUpperCase();
                     return ( aUp == bUp ? 0 : (aUp < bUp ? -1 : 1));      
                }
LVL 4
noamattdAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

IsisagateCommented:
your best bet is probably to put the item into place from the start. So for instance loop through in a for statement the node list you are looking at and find the position in the array where the next element is > then the one you are putting in
then use the

node.insertBefore(); function and insert the new node where it should go. If a position isn't have it add the node to the bottom of the list. This will reduce the overall operations and copying etc.
noamattdAuthor Commented:
Okay, I dig what you're saying.  Can you give me some sample code?  If possible I'd like to find the insertion point via binary search since, as I said, these are large lists.
maclemaCommented:
Heres the fasest way I know of.

Times in seconds...

Sorting 1000 Items:
  IE: 1.312
  FF: 1.109

Heres the test page with html and javascript:
-----------------------------------------------------------

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
<title>Untitled Document</title>
<script type="text/javascript">
function randomString()
{
      var r = Math.floor(Math.random()*99999) + "";
      var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
      var str = "";
      
      for ( var i=0; i<r.length; i++ )
      {
            var n = r.charAt(i);
            str += chars.charAt(n);
      }
      
      return str;
}

function generateList(numOfElems)
{
      var list = document.getElementById("theList");
      i = numOfElems;
      do
      {
            var e = document.createElement("li");
            e.innerHTML = randomString();
            list.appendChild(e);
      }while(i--)
}

//determines how to get the object innerText property
var useInnerText = true;

function init()
{
      generateList(1000);
      
      //determine how to access innerText
      var objTest = document.createElement("li");
      objTest.innerHTML = "A";
      useInnerText = (objTest.innerText) ? true : false;
}
window.onload = init;


//sorting methods
function sortDomList(listID)
{
      var now = new Date();
      var start = now.getTime();
      
      var arr = new Array();
      var list = document.getElementById(listID);
      var i = list.childNodes.length-1;
      do
      {
            var listItem = list.childNodes[i];
            arr.push(listItem);
            list.removeChild(listItem); //remove as we go along
      }
      while(i--)
      arr.sort(itemOrder);
      
      var len = arr.length-1;
      i = arr.length-1;
      do
      {
            list.appendChild(arr[len-i]);
      }
      while(i--)
      
      arr = null; //free up memory
      
      now = new Date();
      var end = now.getTime();
      alert((end-start)/1000);
}

function itemOrder(a, b)     //Sort function,
{
      var aUp, bUp;
      if ( useInnerText == true )
      {
            aUp = a.innerText.toUpperCase();
            bUp = b.innerText.toUpperCase();
      }
      else
      {
            aUp = a.textContent.toUpperCase();
            bUp = b.textContent.toUpperCase();
      }
      return ( aUp == bUp ? 0 : (aUp < bUp ? -1 : 1));    
}
</script>
</head>

<body>
<input name="cmdSort" type="button" value="Sort Now!" onclick="sortDomList('theList');" />
<ul id="theList">
</ul>
</body>
</html>

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Determine the Perfect Price for Your IT Services

Do you wonder if your IT business is truly profitable or if you should raise your prices? Learn how to calculate your overhead burden with our free interactive tool and use it to determine the right price for your IT services. Download your free eBook now!

noamattdAuthor Commented:
maclema,

Looks good and your sample code performed about as well as you described.  I'll try implementing it in my app on Monday and if it works out well I'll give you the points.
maclemaCommented:
Good to hear it is working for you :)
noamattdAuthor Commented:
Worked like a charm, thanks a bunch.
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
JavaScript

From novice to tech pro — start learning today.