Как выполнить сортировку слиянием списков несравнимых элементов?

Question

[makaleks]

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

# Для наглядности пусть будет алфовит
< [a   c   e]
<       [d e f]
< [a b   d]
<   [b c d]

> [a b c d e f]

При возникновении противоречия пусть используется более раннее правило.

Как называется эта задача, но главное - как решается? Есть некоторые мысли, но это надо вести зависимые и независимые списки (как если бы подавалось в порядке [a b],[c d], и гадай кто спереди кто сзади) или для каждого элемента заводить список каких элементов он больше или меньше - но кажется я переусложняю и, как обычно, можно проще. При необходимости поправлю формулировки.

Спасибо

Comments

[Rsa97]

Если нельзя сравнить элементы, то сортировка смысла не имеет. Сортировка - это расстановка элементов в порядке, при котором предшествующий элемент меньше или равен последующему по какой-то метрике.

Answer 1

[Wataru]

Что значит, несравнимых элементов? Типа, вы знаете, что элементы каждого списка строго упорядочены, но про разные элементы из разных списков ничего сказать не можете, только если косвенно?

Наверно, это задача на сортировку при частичном порядке.
Решается через топологическую сортировку графа. Для каждой "буквы" заведите вершину. Проведите направленные ребра между каждой парой соседних элементов в каждом списке. Топологически отсортируйте граф. Работает за линейную сложность.

Comments

[makaleks]

Всё так, всё понятно. Спасибо!

Объяснение сортировки в своё время проще зашло хабровское, ни в коем случае не Вам в укор, лишь для тех, кто дойдёт до этого коммента в поисках