The video you linked already shows the solution I would suggest: split large objects into a standard tile size. This increases the overall number of objects, but allows you to use more standard sort. That would make it easier to explore updating just the moving objects. Traditional sorts tend to have n*log n performance which can beat linear (n) performance under some circumstances. Performance is mostly dependent on a smaller n, but the nature of the data can also be a factor. Some sorts perform very well on data that's mostly sorted. If most of the objects aren't being moved, you could use the previously sorted data as starting point and update the moving objects.

If you want to stick with a topological search, there's been some research on dynamic topological sorts. I noticed that some of the work by David J. Pearce and Paul H.J. Kelly has been used in Tensor Flow and is open source, so that might be a good place to start. I personally haven't seen it discussed much in the game development related research I follow and I wonder if the Computer Science Stack Exchange community might have better answers regarding topological search.

There's also been some research on GPU based topological sorting. D. Svantesson and M. Eklund found thier GPU implementation was only better for large, shallow graphs (pseudo code available). The other paper I looked at by Rahul Saxena, Monika Jain and D.P. Sharma also had some graph restrictions. As such, I'd try other solutions before exploring GPU implementations.

Lastly, consider if there's a game design or game mechanics solution instead of an algorithm solution. It's not uncommon for games to limit things (number of sprites, simultaneous sound effects, ...) based on engine or computational constraints. This could be a hard limit on the number of objects that can be spawned or using something like special foreground objects (clouds or foliage maybe) to quickly exclude some objects from the topological sort via a bounding box. We would need to know more about the specifics of your game to give specific applicable recommendations.

The video you linked already shows the solution I would suggest: split large objects into a standard tile size. This increases the overall number of objects, but allows you to use more standard sort. That would make it easier to explore updating just the moving objects. Traditional sorts tend to have n*log n performance which can beat linear (n) performance under some circumstances. Performance is mostly dependent on a smaller n, but the nature of the data can also be a factor. Some sorts perform very well on data that's mostly sorted. If most of the objects aren't being moved, you could use the previously sorted data as starting point and update the moving objects.

If you want to stick with a topological search, there's been some research on dynamic topological sorts. I noticed that some of the work by David J. Pearce and Paul H.J. Kelly has been used in Tensor Flow and is open source, so that might be a good place to start. 

I personally haven't seen it discussed much in the game development related research I follow and I wonder if the Computer Science Stack Exchange community might have better answers regarding topological search. There's also some topological sort question on Stack Overflow, so that might also be a consideration. If you do ask another site, please tailor your question to that community - asking the same question across multiple Stack exchange sites (also known as cross-posting) is generally not allowed & will typically result in having your question closed.

There's also been some research on GPU based topological sorting. D. Svantesson and M. Eklund found thier GPU implementation was only better for large, shallow graphs (pseudo code available). The other paper I looked at by Rahul Saxena, Monika Jain and D.P. Sharma also had some graph restrictions. As such, I'd try other solutions before exploring GPU implementations.

Lastly, consider if there's a game design or game mechanics solution instead of an algorithm solution. It's not uncommon for games to limit things (number of sprites, simultaneous sound effects, ...) based on engine or computational constraints. This could be a hard limit on the number of objects that can be spawned or using something like special foreground objects (clouds or foliage maybe) to quickly exclude some objects from the topological sort via a bounding box. We would need to know more about the specifics of your game to give specific applicable recommendations.