Ok, in Google Spreadsheets:
I created an initial spreadsheet that should look like this (taking some artistic liberties). The bottom half is yet to be sorted and as such, is equal to the upper half:
Select the three columns that make the Category 1, then go to
Data > Sort range.
From there, just change the preset column (should be A) to C (aka, the 2nd criteria).
This part of the table is now sorted according to the 2nd criteria. Just repeat to the 2nd category.
The end result should be your table.
Based on @beroe suggestion, I was able to make up a little more.
First of, you need to add an extra column, that assigns Individual Categories to each of the items. Although this is feasible with your current data setup, I find it is the Right Thing To Do to have a table such as the following:
Note that I haven't yet sorted the data according to your 2nd criteria. Note also that next to the 2nd criteria is now a column that contains each item's respective Category.
Select all data, then go to
Data > Sort Range. In there Sort first by column D (the column with the Categories), after press add another sort column, and then add the column corresponding to the 2nd criteria (column C).
Why this works is because of an idea spreadsheet software has about precedence. As it is, Google will try to sort first by the column D. Afterwards, it will sort all remaining data by column C. All remaining data is already sorted.
Note that the order by which I placed the columns is this, due to the reason pointed before. If you tried to place Column C then column D, you wouldn't have your desired outcome.
The end result is something like this:
Ultimately, adding a column with the item's information is a good spreadsheet design decision (if there is something like this in existence).