I, too, recently needed a rectangle packing algorithm to stuff images into an overall palette. I was thoroughly surprised to discover that truly optimal rectangle packing is an area of active research. It appears that this paper describes the current cutting-edge solution. What again surprised me was that packing even 20 rectangles took over 15 minutes! So, even applying a state of the art constraint satisfaction problem solution algorithm, the problem is still very difficult.

I suppose the moral of my research is that any decent (read: works well enough for you) heuristic solution should be fine, and that implementing a genuinely optimal algorithm is likely infeasible for packing even small numbers of elements.

Quote:15 minutes! Mine seems to pack about 50 rectangles of various sizes, neatly and instantly. Seems strange.

The paper deals with optimal rectangle packing. Your method may be fast, but hardly optimal.