yes of course sorting is slow, when comparison is slow, but most of the time
comparison is not too complicated. For the following use case, there is a way
to reduce the calculation costs. (warnig all non tested pseudocode, not even
checket if I use sort correctly)
var someData: seq[A] = ...
proc cmp(lhs,rhs:A): int = cmp(someComplexCalculation(lhs),
someComplexCalculation(rhs))
result = someData.sort(cmp)
to something like this:
var someData: seq[A] = ...
var tmp = newSeq[tuple[index:int, value: B]](someData.len)
for i,val in someData:
tmp[i] = someComplexCalculation(val)
proc cmp(lhs,rhs : tuple[index:int, value: B]): int = cmp(lhs.value,
rhs.value)
tmp.sortInplace(cmp)
for i,val in tmp:
result[i] = someData[val.index]
now the someComplexCalculation is only used _N_ times, instead of _N log N_
