Краткий ответ

Компаратор для сортировки должен задавать строгое слабое упорядочивание. Иными словами, результат сравнения должен быть непротиворечивым: элемент не может быть меньше самого себя, отношения должны быть транзитивными, а эквивалентность элементов по компаратору — устойчивой.

Если это требование нарушено, Swift не обязан получить корректно упорядоченный массив: результат может зависеть от реализации алгоритма и порядка вызовов компаратора. Это не обязательно приводит к ошибке выполнения, поэтому такой дефект особенно коварен.

Исторический контекст

Обобщённые алгоритмы сортировки работают с любыми типами элементов и не могут заранее знать, что означает «меньше» для конкретного объекта. Поэтому Swift принимает замыкание-компаратор, описывающее отношение порядка.

Такой подход позволяет сортировать модели по разным критериям без изменения самих моделей. Но алгоритм сортировки предполагает, что переданное отношение обладает математическими свойствами порядка; без них невозможно гарантировать корректный результат независимо от внутренних оптимизаций.

Постановка проблемы

Ошибка возникает, когда компаратор зависит от изменяемого внешнего состояния, возвращает разные результаты для одной пары элементов или задаёт циклическое отношение. Например, он может считать A меньше B, B меньше C, но одновременно C меньше A.

Нельзя также бездумно использовать отношение «элементы не равны» как проверку порядка: для двух разных элементов оно будет истинным в обе стороны. Сортировка ожидает не просто булево условие, а согласованное отношение между каждой парой элементов.

Подробное решение

Компаратор должен удовлетворять следующим условиям:

для любого элемента сравнение его с самим собой должно быть ложным;
если A меньше B, то B не должен быть меньше A;
если A меньше B, а B меньше C, то A должен быть меньше C;
элементы, которые компаратор считает эквивалентными, должны образовывать согласованные группы.

Сортировка может вызывать компаратор в любом порядке и неоднократно. Поэтому замыкание должно быть детерминированным и не должно менять состояние, влияющее на последующие сравнения.

Компаратор не обязан быть связан с Comparable, но его логика должна задавать полный используемый критерий порядка. Если основной критерий допускает равенство, для детерминированного результата можно добавить вторичный критерий:

struct Task {
    let priority: Int
    let id: Int
}

let ordered = tasks.sorted {
    if $0.priority != $1.priority {
        return $0.priority < $1.priority
    }
    return $0.id < $1.id
}

В этом примере сначала сравнивается приоритет, а при его совпадении — идентификатор. Важно не путать эквивалентность по компаратору со стабильностью сортировки: если два элемента считаются эквивалентными, Swift не обязан сохранять их исходный порядок.

Ситуация из практики

В очереди задач требовалось сортировать элементы по приоритету. Первый вариант сравнивал только приоритет. Он был корректным, но задачи с одинаковым приоритетом могли менять относительный порядок после сортировки.

Рассматривались два решения. Можно было оставить только основной критерий: это проще, но результат между запусками или после изменения реализации алгоритма не обязан быть детерминированным. Можно было добавить сравнение по уникальному идентификатору: выражение становится немного длиннее, зато порядок полностью определён.

Выбран второй вариант. Он сохраняет корректность строгого слабого упорядочивания и устраняет неоднозначность для задач с одинаковым приоритетом. В результате тесты и отображение очереди перестали зависеть от исходного порядка элементов.

Что кандидаты часто упускают

Обязан ли компаратор задавать полный порядок без эквивалентных элементов?

Нет. Строгое слабое упорядочивание допускает эквивалентные элементы: для них компаратор возвращает false в обоих направлениях. Полный порядок нужен только тогда, когда приложению требуется однозначное положение каждого элемента; его можно получить добавлением вторичного критерия.

Считается ли сортировка стабильной, если компаратор корректен?

Нет. Корректный компаратор гарантирует соблюдение заданного отношения порядка, но не обязан сохранять исходную последовательность эквивалентных элементов. Если стабильность важна, её нужно обеспечить явно, например включив исходную позицию или другой уникальный критерий в сравнение.

Почему компаратор, зависящий от внешнего изменяемого состояния, опасен даже без явного цикла?

Алгоритм сортировки может сравнивать одну и ту же пару в разные моменты и получать разные ответы. Тогда отношение перестаёт быть фиксированным: уже проверенные выводы могут противоречить последующим сравнениям. Итогом становится отсутствие гарантии по порядку, а не обязательно диагностируемая ошибка, поэтому состояние, влияющее на сравнение, следует зафиксировать до начала сортировки.