That does sound like magic. If I made the following three commits in order, how would it figure out that the last commit depends on the first commit but not on the second one?
That's not the sense of "depends on" that applies here. It's a textual relationship- in this case, I believe the last commit would depend on the second, which would depend on the first.
If you're familiar with CRDTs, they're closely related. Patches store enough information to commute, so a given state (e.g. a branch) can be described purely by a set of patches.
Without understanding the theory behind it, it sounds a lot like magic, but apparently it works.