How can I sort DOM elements triggering the least amount of reflow?

Question

I've got the following example.

<div class="parent">
  <div data-id="5"></div>
  <div data-id="2"></div>
  <div data-id="3"></div>
  <div data-id="1"></div>
  <div data-id="4"></div>
</div>

If I want to order these div's in an ascending order (1,2,3,4,5). I would normally do a loop and append the div's in order to the parent div. This will however mean I always make 5 changes to the dom (regardless of the order of the div's), one for each div.

You can however use the .insertBefore() method to order the div's correctly with only 2 changes!

5,2,3,1,4
Insert 1 before 2
5,1,2,3,4
Insert 5 behind 4 (using .insertBefore() and .nextSibling)
1,2,3,4,5 

Question 1 By making only 2 changes to the DOM I assume less reflow ocours, making the '2 change' sorting action faster than the '5 change'sorting action. Is this correct?

Question 2 What sort of method/algorithm would be able to figure out to only do the insert 1 before 2 and 5 behind 4?

Question 3 (bonus) Will this 'optimized' algorithm still be faster as the amount of items incease? Range 10 - 100 - 1.000 - 10.000 - 100.000

Maybe to clarify: I am not searching for a way to figure out the order (1,2,3,4,5) in the most optimal way. At a certain point I know the order but I want to compare the order agains the order of the div's and THEN figure out the least amount of operations.

Answer 1

Remove all nodes from the DOM and replace them in the right order after you sorted them in your code.

HTML:

<div id="wrapper">
  <div id="par" class="parent">
    <div id="5">5</div>
    <div id="2">2</div>
    <div id="3">3</div>
    <div id="1">1</div>
    <div id="4">4</div>
  </div>
</div>

Javascript:

var clone = document.getElementById("par")
  .cloneNode(true)
var childs = [].slice.call(clone.children);
var sorted = childs.sort(function(a, b) {
  return parseInt(a.id) - parseInt(b.id)
})
var frag = document.createDocumentFragment();
sorted.forEach(function(el) {
  frag.appendChild(el)
})

var wrapper = document.getElementById("wrapper");
wrapper.removeChild(document.getElementById("par"));
wrapper.appendChild(frag);

Explanation: A single DOM manipulation is way heavier than an algorithmic step in your sorting algorithm.

If numbers get large, the smartest sorting algorithm takesO(n log n) times the amount of nodes. This means n*log(n) DOM manipulations. In human language, that is just a couple times more operations than the amount of nodes.

But if you simply remove all nodes, and then add them again in the right order, you get n + 1 DOM operations, at worst. Probably you can add all nodes together, and you will end up with a figure closer to 2 / O(1), but I'm not that specialised in how quickly this is actually done by modern browsers, so let's stay with n + 1, conservatively.

Now on to the numbers:

Say you have 5 nodes. In this case, everything is fine, numbers are small, but for your own peace, and the future peace of you and your colleagues, you want to write a clear algorithm. So delete all nodes and replace them in the right order.

Now say you have 1000 nodes. In this case, sorting will take you about 10,000 operations (n * log n = 1000 * 10) **. If you put each node in there separately, you will have 10,000 DOM manipulations.

Instead, if you just remove the nodes from the DOM, sort them in your javascript code, and then put them back in, you will only have 1000 DOM manipulations. This is quite conservative, because I have the feeling it actually just takes 2 DOM manipulations: one time removing all nodes and one time adding all nodes in the right order***

** I rather give hard figures just to make some sense of it all. Based on base 2 of 1024, which is 10 *** This is probably where the real difference lies. If people know, please comment / edit!

Answer 2

Please take a look at this code.

Basically it removes the container from the dom, applies sorting, reinserts it into the dom.

Usually this all can happen within one frame redraw so it won't affect the length of the page/scroll issues

+function() {
  /**
   * Finding thing wrapping class
   */
  var $con = $('#container');
  /**
   * getting the parent of the wrapping class so we can reinsert when we're done.
   */ 
  var $parent = $con.parent();
  /**
   * Removing container from dom so we can sort in speed
   */   
  $con.remove();
  
  /**
   * Getting the things we need from container that we need to sort
   */
  var $tosort = $con.find('.thing');
  
  /**
   * Apply sorting algorything, get a newly sorted list
   */
  var $neworder = $tosort.sort(function(a,b){
     return parseInt(a.innerText) > parseInt(b.innerText);
  });
  /**
   * Simply append the newly ordered list. They are the same objects, not clones so they'll fit into the right order.
   */
  $con.append($neworder);
  /**
   * Reinsert container into the dom.
   */
  $parent.append($con);
}()

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div id="wrap">
  <div id="container">
    <div class="thing">
      4
    </div>
    <div class="thing">
      3
    </div>
    <div class="thing">
      1
    </div>
    <div class="thing">
      5
    </div>
    <div class="thing">
      2
    </div>
  </div>
</div>

Answer 3

Be more confident in browsers’ capabilities.

1. Browsers batch together DOM operations when they are performed in one single, synchronous execution of a JavaScript sequence. Exceptions occur when you explicitely (and sometimes unknowingly) request a reflow by accessing DOM properties/methods that require the DOM to be up-to-date, e.g. innerWidth, offsetTop, or getBoundingClientRect. See Rendering: Repaint, Reflow, Restyle for details.
   Deleting DOM nodes is not necessary. Add them to a newly created DocumentFragment, they’ll be automatically removed from their current position in the DOM.

2. Browsers, more specifically JS engines, already know and use the smartest sorting algorithm. Save for very specific cases, you don’t need to know about the inner mechanisms of a sorting operation. Just use Array.prototype.sort, provide a custom function if necessary, and watch magic happen.