While Javascript itself is executed very fast on modern browsers, DOM manipulation still takes a lot of time. Moreover, during extensive DOM manipulations some browsers appear to be freezing. And that is something no web developer will want to happen as it dramatically reduces user experience.

So what to do about it? The solution is to change all operations working with DOM to an O(n) performance. The sorting itself is done on pure javascript arrays and objects.

You can use the following sort map function on any javascript array or pseudo-array. pseudo-arrays need to have a .length property and all elements must be accessible using zero-based numeric indices. It does not change the array itself; it generates an index map to the original array instead. You can use that index map as a sorted view of the original array.

The example is using JQuery but the sort function does not.

/*
  create_sort_map   creates a map to iterate through a sorted view 
                    of list
  list              an array or pseudo-array containing all elements
                    to sort
  prop_fn           a callback function that returns the property to
                    sort by for each element of list
  invert            optional: sort descending 
  prev_sortmap      optional: previous result of create_sort_map, if 
                    you want to sort a list multiple times for 
                    different criteria 
  
  Usage example (JQuery):
  
  // find the table to sort
  var table = $('#my_table');
  // find rows to sort
  var list = table.find('tr');
  // created map to sort the list of rows
  var map = create_sort_map( list, 
    function(my_tr) {
      // find the value to sort by inside a row
      return $(my_tr).find('td.my_sort_col').text();
    });
  // re-insert rows in proper order
  for(var i=0; i<map.length; i++) {
    table.append($(list[map[i]]).detach());
  }
  // clean up
  table=list=map=undefined;

  HTML schema for example:
  
  <table id="my_table">
    <tr>
      <td>
        Some text...
      </td>
      <td class="my_sort_col">
        Sort this!
      </td>
    </tr>
    <tr>
      <td>
        Some other text...
      </td>
      <td class="my_sort_col">
        Sort this too!
      </td>
    </tr>
  </table>    
  
  The usage example can be further improved by removing the whole 
  table from page DOM before sorting and insert it back when all 
  sorting is done.
*/
                      
function create_sort_map(list, prop_fn, invert, prev_sortmap) {
  // make sure invert is a valid boolean if not specified in call
  invert = !!invert;
   
  // arr is the sort map that will be created
  var arr=[];
  // list_prop is an array containing all results of prop_fn
  // this makes sure prop_fn is called O(n)
  var list_prop=[];
  
  // is prev_sortmap an array that matches the length of list?
  if(prev_sortmap!==undefined && list.length==prev_sortmap.length) {
    // then use prev_sortmap as starting point for our new sort map
    arr=prev_sortmap;
    // make the list of all prop_fn results
    for(var i=0;i<list.length;i++) {
      list_prop.push(prop_adjust(prop_fn(list[i])));
    }
  }
  else {
    // if prev_sortmap is invalid, use an identity map as starting 
    // point and make the list of all prop_fn results
    for(var i=0;i<list.length;i++) {
      arr.push(i);
      list_prop.push(prop_adjust(prop_fn(list[i])));
    }
  }
  
  // this is pure javascript, it executes quickly although it's a 
  // very slow sort algorithm, O(n^2): Bubblesort
  // change to quicksort if it actually takes more than a few ms
  var changed=true;
  while(changed) {
    changed=false;
    for(var i0=0;i0<(arr.length-1);i0++) {
      var i1=i0+1;
      if(invert ? (list_prop[arr[i0]]<list_prop[arr[i1]])
                : (list_prop[arr[i0]]>list_prop[arr[i1]])) {
        changed=true;
        var xchg=arr[i0];
        arr[i0]=arr[i1];
        arr[i1]=xchg;
      }
    }
  }
  
  // return the sort map
  return arr;


  // prop_adjust is a helper function to introduce general search 
  // rules.
  // for example: 
  // * convert numbers in strings to numbers
  // * application sort rules. 1: basement, 2: main-floor,
  //                           3: first floor, ...
  // it's inside create_sort_map to keep global namespace clean
  function prop_adjust(prop) {
    if(sort_isNumber(prop)) {
      return Number(prop);
    }
    
    prop=prop.toLowerCase();

    // insert application sort rules
		
    return prop;
  }
  
  // is it a number? change depending on your application.  
  function sort_isNumber (o) {
    return !isNaN(o-0) && o !== null && o !== undefined;
  }
}