title: How does Array.sort() behave if comparison function is not transitive?
body: <p>I'm writing an algorithm to sort an array of 3D boxes for drawing in front-to-back order.  There is a well-defined, stable way to decide which of two boxes is in front of the other, so I have written a function to do that, and then I pass my function to <code>Array.prototype.sort()</code> to get the correct drawing order.</p>
  
  <p><a href="https://i.stack.imgur.com/t4sYr.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/t4sYr.png" alt="three boxes overlap each other"></a></p>
  
  <p>But it is possible to have cycles of boxes such that <code>A&gt;B</code>, <code>B&gt;C</code> and <code>C&gt;A</code> are all true.  This means there is no well-defined sort order for the overall list, even though the order of any pair is well-defined.</p>
  
  <p>In practice, this situation is unlikely to arise, and if it does, I can live with one or two boxes being in the wrong order.  But are there JS implementations out there that could sort the whole list wrongly, or crash, under this circumstance?</p>
  
  <hr>
  
  <h2>Update 10 Nov 16</h2>
  
  <p>Just to fill in some more context now the project is done (in fact, no reason you can't <a href="http://kunstwerk-stadionplein.nl/?001000" rel="nofollow noreferrer">look at it</a> if you want):</p>
  
  <p>The reason I asked the question is that, although the obvious answer is "you can't sort using a broken comparator", still... this is a sorting-like task, and attempting to do the sort <em>does</em> give somewhat useful results.</p>
  
  <p>In my specific application, the cyclic case shown above never actually arises (at least, you'd have to be really trying).  My hope was that I could sort the objects such that, if you removed any elements that were part of a cycle, the remaining elements would be in strictly correct order.  But I didn't get to that point, and here's why:</p>
  
  <p>My first idea was that when I compare two boxes, whichever box is in front on the X axis <em>or</em> the Y axis <em>or</em> the Z axis is sorted in front.  But this means that instead of comparing boxes (A), I'm really comparing infinite cross-shapes (B):
  <a href="https://i.stack.imgur.com/4L3Ae.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/4L3Ae.jpg" alt="Overlapping boxes"></a></p>
  
  <p>--which means they overlap like crazy, and the cyclic situation is not rare at all; in fact it's so common that, with 3 or more objects, I might as well use a random order.</p>
  
  <p>At some point I saw <a href="https://shaunlebron.github.io/IsometricBlocks/" rel="nofollow noreferrer">this helpful reference</a>, which suggested that I should only test pairs of boxes that actually overlap on screen.  Adding that test (and sorting boxes as "equal" if they don't overlap) gave better results, with boxes in the right order more often than not, but still with lots of errors.</p>
  
  <p>The problem is that <strong>fast sorting algorithms don't test every possible pair of values</strong> (they'd be O(n<sup>2</sup>) if they did).  Sorting A and B as "equal" doesn't simply mean that their relative order is unimportant; it means that if C sorts before A, it must also sort before B.  No matter what sort algorithm a browser uses, it will skip comparisons based on this assumption, and therefore it will not test every pair of boxes that I need it to test.</p>
  
  <p>In the end, I wrote my own inefficent, naïve sorting code (test every box until I find an overlap).  I never have more than 40 objects on screen, so the performance is OK, and the result is correct often enough.  A more thorough algorithm would involve backtracking, and would raise halting issues, so I stopped here.</p>
  
  <p>So, not the most satisfying conclusion, but sometimes that's how it goes.  Hopefully this will provide some help (or cruel amusement) to someone else, anyway.</p>