Tape sort on 4k-by-4k matrix

Q: How to transpose row-major 4k-by-4k matrix stored on magnetic tape?

A: First prepend the column and row numbers to each element, then tape sort by column numbers then by row numbers, then remove the column and row numbers.
For example: there is a row-major matrix stored on the tape

3 2 1
4 5 7
6 2 3

So on the tape it will be like {3,2,1,4,5,7,6,2,3}

Prepend column and row numbers to each element:
[0,0]3 [1,0]2 [2,0]1
[0,1]4 [1,1]5 [2,1]7
[0,2]6 [1,2]2 [2,2]3

Sort by column number then by row number, on tape it will be like

{[0,0]3,[0,1]4,[0,2]6, [1,0]2,[1,1]5,[1,2]2, [2,0]1,[2,1]7,[2,2]3}