Лучший алгоритм сортировки для случая, когда многие объекты имеют отношения «безразличие» друг к другу

У меня есть необычный случай сортировки, о котором я мало что узнал. Вот параметры:

1) Контейнер произвольного доступа. (Вектор C ++)
2) Обычно небольшой векторный размер (менее 32 объектов)
3) Многие объекты имеют отношения «безразличие» друг к другу, но они не равны. (т.е. им все равно, какой из них появится первым в окончательном отсортированном векторе, но они могут по-разному сравниваться с другими объектами.) Иными словами (если все еще неясно), функция сравнения для двух объектов может возвращать 3 результата: «порядок правильный», «необходимо изменить порядок» или «все равно».
4) Равенство возможно, но будет очень редко. (Но это, вероятно, будет рассматриваться как любое другое «безразличие».
5) Оператор сравнения намного дороже, чем перемещение объекта.
6) Нет разницы в скорости сравнения для определения того, заботятся ли объекты друг о друге или нет. (т.е. я не знаю способа сделать более быстрое сравнение, которое просто говорит, заботятся ли 2 объекта друг о друге или нет.)
7) Случайный порядок запуска.