Sort And Build

I was reading a computational geometry textbook the other day. And, in the first chapter, the author made an offhand comment. Something along the lines of "This is the standard way we build algorithms in computational geometry. First we sort the input data, then we construct the solution incrementally."

And a few moments ago, I was thinking about state space search (for games) and I realized that much the same thing is true. One sorts, builds, sorts, builds, ....

Which suggests to me that there's a general approach to algorithms here: When you're not sure what to do, sort the data and deal with it piecemeal.

The big question: Is this a generally applicable pattern? Or is it only for certain restricted domains like, say, AI and Computational Geometry?

Is sorting a more powerful tool than I had hitherto realized? What other algorithmic patterns use sorting? -- WilliamGrosso

Is sorting taken to mean separating as opposed to ordering? -- WardCunningham

I'm a little confused as to how to read the above with sorting meaning separating but not especially ordering. However, in computer graphics real time simulators, we used to organize the polygons in special ways to simplify their processing. This would count as separating the data into groups, and then working on the groups separately. We also ordered the groups, and within groups when we could. --AlistairCockburn

Don't sorting and separating fall under the more general banner of organizing? The general approach to many problems is to first organize data (e.g., sort it, separate it into piles, structure it for quick retrieval or efficient querying), and then to analyze or process the aggregate. SortAndBuild might be the trivial case of DivideAndConquer. --DaveSmith

I meant "ordering" by sorting. And this may be just as trivial as DaveSmith says, but it still struck me as interesting.

When you're designing objects, you can use a laundry list of questions in order to guide the process, suggest object structures, and make sure you haven't overlooked anything that commonly occurs.

What I'm starting to sense is that there is a similar list of questions and, possibly, patterns at a much lower level (I knew that patterns scaled up, but didn't really suspect they scaled down. My natural stupidity shining forth, I guess).

WilliamGrosso