In-place matrix transposition using rotations
After the array is rotated with dst == N - 1 (so the condition (dst + 1) % N == 0 is about to fire), the tail of the array starting from index N looks like a representation of a N×(M-1) matrix with the values of the original matrix without the first column:

11 21 31 12 13 14 15 22 23 24 25 32 33 34 35
         ^ starting from here


looks like a representation of the

12 13 14 15
22 23 24 25
32 33 34 35


matrix

which immediately suggests how to simplify the algorithm:

template&lt;typename T&gt;
void inplace_transpose_using_rotations(T* matrix, int N, int M)
{
    if (N == 1 || M == 1)
        return;

    for (int dst = 1; dst != N; dst++)
        std::rotate(matrix + dst, matrix + dst * M, matrix + dst * M + 1);

    inplace_transpose_using_rotations(matrix + N, N, M - 1);
}


This explains how the algorithm works: rotations move first elements of each row into their proper position in the transposed matrix and at the same time shift the other elements to the right forming a representation of a smaller N×(M-1) matrix in the right side of the array. Then this smaller matrix is transposed, until we get a N×1 matrix.