Originally Posted by Megol
Obviously true for anybody with some programming education. Unless one have a problem with (almost) sorted data
well you would hope, but apparently not...
a lot of programmers actually don't have a programming education, i have worked with a lot of people with a scientific or mathematical background, especially physics (which is also my background). Often you learn some programming on those courses, but they don't go through such stuff as time complexity in detail. I'm glad i picked up a book on the subject. really the bit that changed my entire worldview was where it said that it becomes more
important as computers get faster, not less, which is the subtlety that a lot of people miss, i think. "Ah i have 3GHz CPU so i don't have to care about efficiency" yeah but you also have 4Gb of data so yeah, you do, and double
BTW there are ways to deal with (almost) sorted data. There's also heapsort of course, which has no such problem with worst-case scenarios (although it has problems of its own, like probability of cache misses).