Based on T180076: API:Usercontribs has inconsistent ordering The Usercontribs API should allow clients to order by timestamp (first) rather than user id.

To do this properly, the database query would have to be a UNION of individual queries per user that is then sorted and limited, e.g.

(SELECT ... FROM page, revision WHERE rev_user = 1 ORDER BY rev_timestamp, rev_id LIMIT 501)
UNION ALL
(SELECT ... FROM page, revision WHERE rev_user = 2 ORDER BY rev_timestamp, rev_id LIMIT 501)
UNION ALL
(SELECT ... FROM page, revision WHERE rev_user = 3 ORDER BY rev_timestamp, rev_id LIMIT 501)
...
(SELECT ... FROM page, revision WHERE rev_user = 500 ORDER BY rev_timestamp, rev_id LIMIT 501)
ORDER BY rev_timestamp, rev_id LIMIT 501

This won't be possible when combined with ucuserprefix, of course, since that lacks a bounded number of users. Performance may require that we reduce the maximum allowed for uclimit and/or ucuser/ucuserids.

As for implementation, once the transitional code being added in Gerrit change 380669 is removed we should be able to do it with ApiQueryBase::doSelect() much like what's being done in Gerrit change 359501.