Optimal in-place transposition of rectangular matrices (Q2272153)

A method is given for transposing (in place) a rectangular \(m\) by \(n\) matrix stored as a two dimensional array. The focus is on minimizing the number of operations and the number of additional memory cells other than used in storing the given matrix. The proposed method uses \(O(mn)\) writes and \(\min(m,n)\) auxiliary memory cells. The algorithm for square matrices (\(m=n\)) is discussed.