What you describe sounds a lot like clustering. Start for example by trying out hierarchical clustering.
Your original question:
Use predsort/3 but do not remove equivalent elements
You can trick predsort/3 to not remove duplicates: just make sure your comparison never says two elements are equivalent.
?- [user].
|: my_compare(Order, X, Y) :- compare(Order0, X, Y),
|: ( Order0 == '=' -> Order = '<' ; Order0 = Order ).
|: ^D% user://1 compiled 0.03 sec, 1 clauses
true.
?- predsort(my_compare, [a,b,c,a,b,c], Sorted).
Sorted = [a, a, b, b, c, c].
I am not sure how this helps you with your problem though.