I love this question. As a matter of fact this was one of my first programming projects back in the day. Mind you I was programming it in Turing. If you don't know what it is, probably better not to ask. Syntax was alot like Pascal though.

Anyhow, I don't remember getting it to work, but then again, my programming skills have improved greatly since then. What I'd recommend doing is looking at this like the game Connect Four(google for it if you don't know what that is). If not, put another way, take it a colomn at a time. I becomes manageable this way.

1) A Shot rings out! ...and it's in the dirt!
2) You find the magically floating dirt,
3) You determine how tall each colomn is and how far it has to fall and if you care about animation if there is more than one group of dirt in that colomn,
4) You then redraw your dirt per colomn depending on your animation you want to do.
5) Play on!

Working on one colomn at a time makes it quite easy. You could either count the dirt pixels and do a simple redraw when it comes time to animate or you could actually, from the bottom count the "stacks" of dirt in the colomn and mark the starting point of air so you know where each "stack" must stop. Keep in mind that if you have more than 1 stack you much calculate the starting point of your first air pixel + your 1st stack's height, etc. Doing it the way of the later will give you some animation possiblities, but might slow things down a bit more. Up to you how you want it. If it proves to be too slow however, it might serve you to fall back to the simpler way unless you can optimize things some more.

Traveler is right though, this will be a bit of a pause in your game, I'd imagine that your game is turn based? If so that'd help, if not then I'd recommend a way to speed up and dirt detection in your game with inline ASM or something.

Let me know if you finish your algo, I'm quite interested in how it'll end up.