Coarse collision detection is only expensive if done from a cold start every time. In practice, there's a startup cost of ordering the bounding boxes, but then only a small incremental cost as things move around. Most moves are local, and require only a small number of changes, and many objects in a game don't at all. Here's the classic paper from Ming Lin, from the 1990s.[1]

Fine collision detection can also be done incrementally. Incremental GJK is a good approach. Here's Steven Cameron's paper on that.[2]

I wrote one of those once in C++, using the ordered bounding box approach from Lin and the incremental GJK approach from Cameron, plus some new stuff to guarantee continuity as objects moved. It turns out that incremental GJK has some serious floating point loss of significance problems as faces approach parallel. When you build a physics engine this way, the near-parallel case gets explored very thoroughly as objects settle. Turns out you need a 64-bit FPU. This was a problem on some consoles, and is still a problem on some GPUs.

[1] https://www.cs.jhu.edu/~cohen/Publications/icollide.pdf [2] https://graphics.stanford.edu/courses/cs468-01-fall/Papers/c...