What you described is what I said. A spatial acceleration structure is meant to skip as many comparisons as possible. What you are talking about is trading less sorting and more comparisons during the queries.
Sorry, I misunderstood the "brute force" part of your comment. You are right, for the active elements the standard implementation uses a brute force on the active elements. I had to implement sort-and-sweep to handle one specific performance problem that took 45 seconds to compute. With the simple sort-and-sweep this went down to 100ms. I also tried sorting the active elements along the secondary axis, but at least in our case this did not yield in any further performance improvements. This probably depends a lot on how many elements there are in the active list.
