Most of the time, what you want is not a clever visualization of a complex algorithm, but a simple distillation of its essence. Static diagrams are usually simpler than visualizations. And if you feel the inherent complexity can only be conveyed with animation, it's likely you haven't fully distilled your understanding.
But even in that example, while the animation instantly conveys the high-level idea, it's still a bit magical: "I get what's happening, but not exactly how." To understand in detail what's going on, carefully chosen freeze frames with an explanation would probably be better, especially complemented by the animation. The ability to slow down, reverse, and interact could work too here.
https://youtu.be/yYAw79386WI?t=214
I agree it's a great explanation, and the video format feels right for this. Still, it's not the video per se that makes this great, but the way the concept has been broken down into simple (almost unmoving) parts for you, and is then built up in steps.