I start by doing a lookup, then viewing the lookup as a list (rather than as individual contacts) and clicking on the Company column header to alphabetize (those columns can be customized.) After that, I create the report. Another way is to export the lookup to Excel and sort in Excel.
I tried your suggestion, but the report did not come out sorted. One problem may be that my report is not just one record per line. It has a section for each contact, with name, title, address, and one user-defined field. So there are 5 records per page. It seems the sort order would be an option in the report design, but I don't see it there. Am I missing it in plain view???