// Original JavaScript code by Chirp Internet: www.chirp.com.au
// Please acknowledge use of this code by including this header.

function quickSort(parent, childName, colName)
{
  var parent = parent;			// 'parent' node
  var childName = childName;	// nodeName for 'children'
  var colName = colName;		// nodeName for 'columns'

  // build array of 'child' nodes
  var items = parent.getElementsByTagName(childName);
  var N = items.length;

  // define private methods
  var get = function(i, col, wrapper)
  {
    var retval = null;
    var node = null;
    var sort;

    if(colName) {
      // sort by col'th element of i'th child
      node = items[i].getElementsByTagName(colName)[col];
    } else {
      // sort by i'th child
      node = items[i];
    }

    if(null != (sort = node.getAttribute("sort"))) {
      // use 'sort' attribute if available
      retval = sort;
    } else if(node.childNodes.length > 0) {
      if(wrapper) {
        // sort by contents of first 'wrapper' element in 'child'
        retval = node.getElementsByTagName(wrapper)[0].firstChild.nodeValue;
      } else {
        // sort by 'child' contents
        retval = node.firstChild.nodeValue;
      }
    } else {
      return "";
    }

    if(parseFloat(retval) == retval) return parseFloat(retval);
    return retval;
  }

  var compare = function(val1, val2, desc)
  {
    return (desc) ? val1 > val2 : val1 < val2;
  }

  var exchange = function(i, j)
  {
    if(i == j+1) {
      parent.insertBefore(items[i], items[j]);
    } else if(j == i+1) {
      parent.insertBefore(items[j], items[i]);
    } else {
      var tmpNode = parent.replaceChild(items[i], items[j]);
      if(typeof(items[i]) == "undefined") {
        parent.appendChild(tmpNode);
      } else {
        parent.insertBefore(tmpNode, items[i]);
      }
    }
  }

  var quicksort = function(m, n, col, desc, wrapper)
  {
    if(n <= m+1) return;

    if((n - m) == 2) {
      if(compare(get(n-1, col, wrapper), get(m, col, wrapper), desc)) exchange(n-1, m);
      return;
    }

    i = m + 1;
    j = n - 1;

    if(compare(get(m, col, wrapper), get(i, col, wrapper), desc)) exchange(i, m);
    if(compare(get(j, col, wrapper), get(m, col, wrapper), desc)) exchange(m, j);
    if(compare(get(m, col, wrapper), get(i, col, wrapper), desc)) exchange(i, m);

    pivot = get(m, col, wrapper);

    while(true) {
      j--;
      while(compare(pivot, get(j, col, wrapper), desc)) j--;
      i++;
      while(compare(get(i, col, wrapper), pivot, desc)) i++;
      if(j <= i) break;
      exchange(i, j);
    }

    exchange(m, j);

    if((j-m) < (n-j)) {
      quicksort(m, j, col, desc, wrapper);
      quicksort(j+1, n, col, desc, wrapper);
    } else {
      quicksort(j+1, n, col, desc, wrapper);
      quicksort(m, j, col, desc, wrapper);
    }
  }

  // define public method
  this.sort = function(col, desc, wrapper)
  {
    quicksort(0, N, col, desc, wrapper);
  }
}