I am writing an algorithm for sorting an array of 3D boxes for drawing in front-to-back order. There is a clear, stable way to decide which of the two boxes is in front of the other, so I wrote a function for this, and then I pass my function to Array.prototype.sort() to get the correct drawing order.
But it is possible to have box cycles such that A>B , B>C and C>A all true. This means that there is no clearly defined sort order for the general list, although the order of any pair is defined correctly.
In practice, this situation is unlikely to arise, and if so, I can live with one or two drawers in the wrong order. But are there JS implementations that can sort the entire list by mistake or fail under this circumstance?
November 10, update 16
Just to fill in some more context, the project is now done (in fact, there are no reasons why you cannot look at it if you want):
The reason I asked the question is that although the obvious answer is “you cannot sort using a broken comparator”, still ... this is a sorting task, and trying to pretend really gives some useful results.
In my particular application, the cyclical case shown above never occurs (at least you should really try). I was hoping that I could sort the objects in such a way that if you deleted any elements that were part of the loop, the rest of the elements would be in the strictly correct order. But I did not get to this, and here's why:
My first idea was that when I compare the two fields, depending on which box is in front along the X axis or the Y axis, or the Z axis is sorted in front. But that means that instead of comparing the boxes (A), I am really comparing infinite cross forms (B): 
- which means that they overlap like crazy, and the cyclical situation is not rare at all; in fact, it is so common that with 3 or more objects I could also use random order.
At some point, I saw this useful link , which said that I should only check pairs of boxes that actually overlap on the screen. Adding this test (and sorting fields as "equal" if they do not overlap) gave better results, and the boxes in the correct order are more often than all, but still with a lot of errors.
The problem is that fast sorting algorithms do not check every possible pair of values (they would be O (n 2 ) if they did). Sorting A and B as “equal” does not simply mean that their relative order is unimportant; this means that if C sorts to A, it should also sort to B. No matter what sorting algorithm the browser uses, it will skip comparisons based on this assumption, and therefore it will not test every pair of boxes I need for testing.
In the end, I wrote my own ineffective, naive sorting code (check each cell until I find a match). I have never had more than 40 objects on the screen, so the performance is fine, and the result is quite correct. A more thorough algorithm will include a rollback, and will cause problems with stopping, so I stayed here.
So, not the most satisfactory conclusion, but sometimes how it happens. Hope this provides someone else with some help (or cruel entertainment).