How to implement a natural sort algorithm in c++?

I'm sorting strings that are comprised of text and numbers. I want the sort to sort the number parts as numbers, not alphanumeric.

For example I want: abc1def, ..., abc9def, abc10def

instead of: abc10def, abc1def, ..., abc9def

Does anyone know an algorithm for this (in particular in c++)

Thanks

I asked this exact question (although in Java) and got pointed to http://www.davekoelle.com/alphanum.html which has an algorithm and implementations of it in many languages.

Update 14 years later: Dave Koelle’s blog has gone off line and I can’t find his actual algorithm, but here’s an implementation. https://github.com/cblanc/koelle-sort

Update 14 years and 5 months after the original answer: In the comments, it was pointed out that Dave Koelle’s blog is on the wayback machine at https://web.archive.org/web/20210207124255/davekoelle.com/alphanum.html