The relevant code is:

1. default sort key is page name with stripped namespace name,
2. otherwise sorting is ugly. if( !$isUpload && $pageObj->mTitle->getNamespace() == NS_MAIN ) { $default_sortkey = ""; } else { $default_sortkey = "|{{PAGENAME}}"; }

The "|{{PAGENAME}}" is only added for pages that are not in the main namespace (like file: or category:)

The reason for this probably is/was *) (copied from http://www.mediawiki.org/wiki/Help:Categories#Sort_key )

By default, a page is sorted within a category under the
first letter of its full name _including the namespace_.

In other words: all Template:* pages would be listed under "T".

It seems this changed with current MediaWiki versions - a short look at some random categories in Wikipedia and a wiki I maintain indicates that the default sorting is now by page title _without_ the namespace, but I'm not 100% sure. (Can someone confirm that? - also asked on http://www.mediawiki.org/wiki/Help_talk:Categories)

If you want to test, edit the code (SelectCategory_body.php around line 150). Please replace

$default_sortkey = "|{{PAGENAME}}";

with

$default_sortkey = "";

and tell me what happens ;-)

*) the code for this was added long time before I started to work on SelectCategory

@Cboltz: This issue has been assigned to you a while ago.
Could you please provide a status update and inform us whether you are still working (or still plan to work) on this issue?
Only in case you do not plan to work on this issue anymore, should the assignee be removed? Thanks.