Problem: Because category trees aren't made by one person, things like sort keys may be inconsistent. From the category pages themselves it is often not obvious when the sort keys deviate.
Proposed solution: Show the sort key of every page in the category, maybe in brackets after the link to the page. Because most regular readers probably don't care about sort keys, this should be an opt-in (maybe through a gadget).
