I think the options are (in descending order of probable (usefulness * 1/hassle) / 2):

1. Build and install natsort.
2. Patch GNU sort. Build. Install.
3. When you know you'll just have alpha then numeric then alpha, use the sed and sort mechanism above.
4. Write your own.

The patch for GNU sort from the guy who did natsort is out of date. I talked to the folks in #gnu at freenode, and they said they'd probably consider committing the feature if someone can implement it neatly, and use a nice long option name like --natural-sort (it doesn't deserve a short option apparently... :) )