splitting up and sorting commits?

[Csepp <raingloom@riseup.net>]

Hey all!

I'm working on a fairly sizeable MirageOS branch, just getting the
hello-world kernel running involved adding about 40 packages.  Very
often I run into a scenario where an imported package needs some other
package to compile, and then that needs another, and then that another,
and so on and so on, so by the time I can commit the first I have a
plethora of new packages that should in theory all get their own
commits.
There are two problems with this:
* Splitting up the commit is a pain, even with git add --patch, because
hand editing the diff sucks and splitting does not work, possibly due to
there not being enough space between defines for git's taste.
* It is very easy for package to get added before their dependencies, so
even though by the end of the commit chain everything builds perfectly
fine, there are intermediate commits that can't be tested on their own.

How should one solve this?  I already spent way too much time on a
script that I foolishly thought would be able to automatically sort
commits based on their dependencies, but now I'm throwing in the towel,
it's not getting anywhere.