I find it incredible (literally, I just can't bring myself to believe) that there are people WORKING PROFESSIONALLY as programmers without knowing this extremely basic high-school level fact. Surely every programmer in the world knows that there are different kinds of sorts with different O(n) performance characteristics.
[run-on-sentence]The fact that people are deploying actual products to actual users, without thinking even for a minute about how their choice of algorithm and data structures will perform in large but fully EXPECTED loads is a very sad reflection on the state of the software engineering profession.[/run-on-sentence]
Data structures and algorithms are the ABC of software engineering, of software programming. Thinking a bit ahead is the ABC of any engineering or construction practice. Imagine if the first floor ceiling could easily carry itself, but would collapse if more than 2 people stand on it.
On a different note, the tables you presented are probably easier to grok as graphs. You might even want to show one graph in a linear scale, and one graph in logarithmic scale.