Есть многоугольники на плоскости. Нужно отрисовать это как сцену в изометрии - вытянуть многоугольники в высоту получив призмы. При этом нужно рисовать их в правильной последовательности, чтобы ближние закрывали дальние. OpenGL и z-buffer использовать нельзя. Разбивать призмы нельзя, т.е. выводить каждую только целиком. Порядок призм по условию задачи определяется довольно хитрым образом: о двух призмах мы можем сказать: либо А ближе Б, либо Б ближе А, либо порядок не важен. Причём эта операция не коммутативна: А может считать себя ближе Б, но Б может считать что пересекается с А. Понятно, что в этих условиях некоторые случаи невозможно нарисовать корректно (например, пересекающиеся призмы, или призму в выемке другой, невыпуклой), а некоторые можно нарисовать разными способами (из-за хитрого сравнения) - это нормально.
Собственно вопрос - чем это сортировать. Понятно что стандартный std::sort даст скорее всего непредсказуемые результаты, да и работает он с бинарным предикатом, а нужен тернарный. Кроме этого, сортировка нужна стабильная и эффективно сортирующая (почти) отсортированную последовательность, ибо есть идея при изменении сцены/позиции наблюдателя использовать сортировку с предыдущего кадра которая почти всегда будет подходить в неизменном виде.
Можно было бы использовать самые банальные алгоритмы начиная с пузырька, учитывая что для отсортированной последовательности он даст O(n), но меня беспокоит нестабильность на штуках типа А < Б, Б < В, В < А которые по условию тоже возможны.