search

roarin-roran / Sorting

0 stars 0 forks source link

some sortables can't be compared with infinity #78

Open roarin-roran opened 2 years ago

roarin-roran commented 2 years ago

current methods work for anything which can be compared with both each other and math.inf

test how letters etc react to this - can they be compared to inf in python? if not, need either a custom comparison operator, a new merge method, or a disclaimer.

simplest option: if one element is inf, no comparison is needed - inf is bigger. can do with a try-catch? may be slower than alternatives.

what mergers are there which don't have inf as an option, but don't require extra comparisons?

sebawild commented 2 years ago

I think we will not get around an explicit check for “end of run” when using tournament trees. math.inf was a nice way to get that, but it is not general (and probably just an implicit check for many types of numbers as well).

So the question is only, how can we get this check fast (for the normal case where we are not at the end of the file), and without too much ugly code.

roarin-roran commented 2 years ago

sounds good. this seems like a problem which someone else must have solved, do you know how others deal with this?

sebawild commented 2 years ago

should check Knuth vol 3

sebawild commented 2 years ago

Read over this again; I don't think Knuth says much about the sentinels, other that they could be avoided “at some loss of elegance and efficiency”

roarin-roran commented 2 years ago

we know how to avoid them at that cost :p

roarin-roran commented 2 years ago

what do?

sebawild commented 2 years ago

Explicitly check for end of run