Optimal in-place transposition of rectangular matrices

Given a rectangular m×nm×n matrix stored as a two-dimensional array, we want to transpose it in place and measure the cost by the number of memory writes and the number of auxiliary cells used. We propose a transposition algorithm with optimal complexity O(mn)O(mn) using only min(m,n)min(m,n) auxiliary memory cells.