Performance: detector body sorting

[cha0s]

matter-js/src/collision/Detector.js

Line 72 in f9208df

bodies.sort(Detector._compareBoundsX);

The above code is largely inefficient most of the time in practice. This is because quicksort is generally less efficient on mostly-sorted arrays.

Funny as it may sound, the humble insertion sort is a great candidate for sorting mostly-sorted arrays. This is the case a lot of the time in practice: most objects do not move so far every frame as to essentially randomize the bounds sorting.

Replacing the code above with

  for (let i = 1; i < bodies.length; i++) {
    let current = bodies[i];
    let j = i - 1;
    while ((j > -1) && (current.bounds.min.x < bodies[j].bounds.min.x)) {
      bodies[j + 1] = bodies[j];
      j--;
    }
    bodies[j + 1] = current;
  }

runs almost 25% faster.

You may not agree with this and I'm curious what your opinion is.

Regardless of whether you think this sorting strategy makes sense in a general case, I suggest that the original line of code above is moved to a new method on Detector: sortBodies. If this was done, it would be much easier to swap out a sort that makes sense for your simulation by simply overriding Detector.sortBodies. As it stands today, the entire Detector.collisions method most be overridden to change the sorting strategy for bodies.

Thanks for your work!