It is not rm itself that provides sorted nature; it is an extension of the shell. If you were rm * , the shell would extend this to something like:
rm aaa bbb ccc
and rm will never even see the * argument. By the way, although I'm not sure that sorted behavior is guaranteed for all shells, this is of course for bash , according to the documentation:
... replaced by alphabetically sorted list of file names matching the pattern.
The rm -rf * is a bit of a weird, hybrid case, because even if the shell sorts the entries * , it is still only for the first level entries.
Therefore, rm -rf * can expand to:
rm -rf aa_dir bb_dir cc_dir
but it completely depends on how rm works internally with regard to the processing order of entries in these directories, although, obviously, it is safe to say that all entries in the directory will be deleted until the directory itself.
Most likely, he will just use readdir() or something similar, which will arrange things depending on how they are stored in the "files" of the directory, and not in alphabetical order.
In any case, the order in which they are deleted should probably not matter - they will all be ultimately deleted, provided that permissions allow.