I used DumpSave for a 2D Interpolation Function created by NDSolve and the file is 35MB ... Does that make sense?

The entire notebook is only 18MB

Can this question be improved?

@Mr.Wizard I'm not sure. Maybe a CW "Common performance pitfalls" compendium might be a useful resource, but it may get unmanageably large as the beginner's "pitfalls" question has become. I don't know why n^2 complexity is the boundary point for inclusion or why there should be a boundary point. I think a comparison between common function calls with significant performance differences (e.g. with and without SameTest) might be useful.

The difference between Sort[data] and Sort[data, test] seems to be overhead, not the order of the complexity. But then there is already a question on performance tuning that addresses several issues (vectorization, packed arrays, etc. -- I'll have to look it up).

Also, one may have reasons for preferring an $O(n^2)$ algorithm over an $O(n\log n)$ one: (numerical) stability, simpler (thus easier to debug) implementation, etc.

How come Union and Intersection don't have attribute Orderless? They are Flat which implies associativity all right. But they are also commutative operations, what Orderless implies, if I understand this right.

does GraphData have data for graphs in the style of those in Knuth´s GraphBase? (Who killed who in the Illiad, characters in Anna Karennina, and so on)