Minor Search results of categories and category items are sorted by Relevance only. This makes 2 items with same relevance appearing in random order each time search is made.
In In-Portal versions 5.1.3 and below we also applied default sorting after Relevance one (e.g. by Link Name or Article Title).