I think

acknaka nailed it. Here's the cell formula that does the job, plus a recipe for using it:

1. Alphabetize your spreadsheet,

2. Add an extra column, and put this formula into every cell (this is the silver bullet):

="["&(10000+(1+INT( (ROW()+1-3) /(10*3))))&","&(10000+(3*((1+MOD(ROW()+1-3,10))-1)+(1+INT((ROW()+1-3)/10))))&"]"

Continue adding cells below the data until the total number of rows is a multiple of 30 (10x3). This is to make the last page come out right.

A typical entry will look like this: [10003,10025], which means the 25th label on the 3rd page (printed across, but alphabetized down).

3. Add another extra column, and copy-and-paste VALUES from the first extra column to the 2nd one. You'll probably clone the column header, too, so alter it slightly (perhaps by putting "v" at the end for "values") else the next step is ambiguous.

4. Sort the spreadsheet again, this time on the 2nd new column. And you're done.

5. Print the labels as usual. They are magically laid out just way you want them!

NOTE: This solution easily adapts to other label layouts -- e.g. 11x3 or 10x2 -- or even 4x2 (for name badges, say). The numbers 10 and 3 appear in the formula (several times). 10 is simply the number of rows and 3 is the number of columns in the labels pages.

NOTE ALSO: This solution should work equally well for OpenOffice, for all versions of Word and Excel (I tested ver. 2013), and for other MS-Office-like suites, such as Google's G-Suite Apps (which I haven't tested). Most likely it is the universal solution using just an Excel formula. Comments are welcome on that!

P.S. The 10000 might need more zeros if you're doing more than 9,999 pages of labels