As far as I know, these are three types of data structures that can be used for collision detection broadphase:

1. Unsorted arrays: Check every object againist every object - O(n^2) time; O(log n) space. It's so slow, it's useless if n isn't really small.

   for (i=1;i<objects;i++){
     for(j=0;j<i;j++) narrowPhase(i,j);
   };
   

2. Sorted arrays: Sort the objects, so that you get O(n^(2-1/k)) for k dimensions O(n^1.5) for 2d and O(n^1.67) for 3d and O(n) space.

   Assuming the space is 2D and sortedArray is sorted so that if the object begins in sortedArray[i] and another object ends at sortedArray[i-1]; they don't collide

3. Heaps of stacks: Divide the objects between a heap of stacks, so that you only have to check the bucket, its children and its parents - O(n log n) time, but O(n^2) space.

   This is probably the most frequently used approach.

Is there a way of having O(n log n) time with less space? When is it more efficient to use sorted arrays over heaps and vice versa?