My guess is that recently changed (or recently created) articles are not at the right place in these categories and are added at the beginning of the category instead of the corresponding sort key, but this might be a wrong guess.

Did your wiki by any chance recently asked for changing of category sorting (collation)?

T129411: Run `php maintenance/updateCollation.php --force` on all Russian-language projects using uca-ru collation & T58041: updateCollation.php script prohibitively slow for very large wikis
On ruwiki it was done partially yet AFAIK.
cc: @kaldari

Observation from testing:

Removed sortkey from Тарік Азіз
The order in https://uk.wikipedia.org/wiki/Категорія:Померли_2015 happened to be К (cyr), О (cyr), Т (cyr), S (lat), А (cyr), Б (cyr), В (cyr)
Returned proper sortkey
The order in https://uk.wikipedia.org/wiki/Категорія:Померли_2015 happened to be А (cyr), К (cyr), О (cyr), S (lat), Б (cyr), В (cyr), however, Тарік Азіз is first in the list of "А", while it should be after Вілфрід Агбонавбаре due to proper sorting.

Page purge nor blank edit doesn't enforce proper recategorization.

In T136281#2329459, @Danny_B wrote:

Did your wiki by any chance recently asked for changing of category sorting (collation)?

We asked for it several years ago, and it was done in 2013 ( T43040 ). There were no recent requests for Ukrainian, thus this is definitely not the reason.

I believe Ops is running maintenance/updateCollation.php on all the wikis today. It may be a temporary problem as the script takes anywhere from a couple hours to a couple days to run depending on the size of the wiki.

Yeah, see announcement here: https://lists.wikimedia.org/pipermail/wikitech-l/2016-May/085741.html and information on T86096. This should be fixed by Saturday.

The results in the links in the description seem to be different now, although still not correct. I would suggest giving it 24 hours and see if it is fixed tomorrow.

The script on ruwiki will, by my estimation, start to run tomorrow afternoon and finish sometimes in the evening or on saturday.

The reason is ruwiki is in the database shard, s6, where the two largest wikis affected by the transition reside - frwiki and ruwiki itself.

Unluckily, we can't run more than one wiki in parallel on the same shard since it would risk overloading the database.

Please be patient while we conclude the transition.

The script is running on ruwiki now, I've clearly been too pessimistic last night. I'll report when it is done. @NickK is the situation any better now?

Script has finished running, and as far as I can see, all pages reported in this ticket are now redered correctly.

Thanks, I confirm that the problem is resolved.