I can't sort product collection by category id

I have a few categories: guys, ladies, men, women and offers.

Every product is assigned to guys, ladies, men OR women categories.

And some products are assigned to "offers" category.

I need to retrieve every "offers" products but sort by the others categories, I mean:

OFFERS -> guys products -> ladies products -> men products -> women products

$collection = Mage::getResourceModel('catalog/product_collection')
        ->addAttributeToSort('category_ids', 'ASC')
        ->addAttributeToSelect(array('name', 'sku', 'status', 'visibility', 'is_saleable'));

    foreach ($_productCollection as $_product) {
        echo "<!-- "  . $_product->getName() . '-->';
    }

Right now I am getting the products to display by the category "offers", but this products cames ordered by name attribute and I need those products sorted by category before name.

How can I achieve this?

The following query would return all products and join them against the category-product relation table. It also sorts the records on category_id and position within the category.

SELECT `e`.* 
FROM `catalog_product_entity` AS `e` 
LEFT JOIN catalog_category_product ON(entity_id=product_id)
ORDER BY category_id AND position;

The only thing that can happen is that you run into duplicate products, since products might be in the ladies and woman products category. Though this can simply be prevented by removing the x.catetgory_id from the query and add a DISTINCT to filter duplicates.

The underneath is just a quick mockup of how the collection should look like. You still need to test this. Hope this is a guidance in the good direction for you.

$collection = Mage::getResourceModel('catalog/product_collection')
    ->addAttributeToSelect('*')
    ->joinTable('catalog/category_product', 'entity_id=product_id', array('product_id' => 'product_id'), null, 'left')
    ->addAtributeToSort('category_id');