Is this solution always worth it (barring exceptionally small or simple problems..thinking real world)? Especially with the fine-grained locking solution it didn't really seem to have any massive drawbacks, whereas this solution adds in an additional sort and extra passes over the data. Is the assumption that fine-grained locking can simply be really difficult to implement or that it can add tons of instructions to acquire locks?

In step 3, there will be multiple logical threads. Each thread will be responsible for an index. It is guaranteed that every entry of cell_starts and cell_ends will only be filled by one thread, so no extra synchronization is needed.