2 ms·
I don’t know the history of it, but I can imagine people thinking the same thing about comparison sorts early on; how could you possibly sort a list without com
by mistercow 5y ago
I don’t know the history of it, but I can imagine people thinking the same thing about comparison sorts early on; how could you possibly sort a list without comparing every element to every other element?
I mean, I agree with the conclusion that P probably doesn’t equal NP, if nothing else because we’ve had an awful lot of very smart people looking at it without any inkling to the contrary. But I don’t generally trust “I don’t see how” intuitions with this sort of thing.
- musicale 5y ago> I can imagine people thinking the same thing about comparison sorts early on; how could you possibly sort a list without comparing every element to every other element Maybe people who never tried (or thought about) reshelving library books, sorting/delivering mail, etc..
- Sharlin 5y agoIndeed the very word "sorting" in its general sense means arranging items into categories (ie. equivalence classes) which doesn’t usually involve pairwise comparisons at all.
- gfody 5y ago"I don't see how" can't be trusted coming from someone who hasn't even tried. if you're sorting a pile of stones by weight you quickly learn to leverage the transitive property