How to sort the product?
In Drupal 6, have some solution about sort product.
Use Faceted Search Module, which sort informations from CCK fields
http://facetedsearch.davidlesieur.com/, great and simple module.
Unfortunately does not have this module for D7.
How you sort the products in yours stores?
I think most sophisticated stores use views to present products, and of course it has impressive sorting capabilities.
Sort or categorization?
I assume that you are aware of the product and cart summary view where you can sort, filter regarding taxonomy term, use panels taxonomy template and the view contextual filter upon that.