parallelizable fast matrix in-place transposition
Sorry, no pseudocode, but a recent paper with a fast parallel algorithm, to appear in ACM Transactions on Mathematical Software:

@Article{Gustavson:2011:PCE,
  author =       "Fred Gustavson and Lars Karlsson and Bo K{\aa}gstr{\"o}m",
  title =        "Parallel and Cache-Efficient In-Place Matrix Storage Format
                  Conversion",
  journal =      "{ACM} Transactions on Mathematical Software",
  accepted =     "8 July 2010",
  upcoming =     "true", 
  abstract =     "
                  Techniques and algorithms for efficient in-place
                  conversion to and from standard and blocked matrix
                  storage formats are described. Such functionality is
                  required by numerical libraries that use different
                  data layouts internally. Parallel algorithms and a
                  software package for in-place matrix storage format
                  conversion based on in-place matrix transposition are
                  presented and evaluated. A new algorithm for in-place
                  transposition which efficiently determines the structure
                  of the transposition permutation a priori is one of the
                  key ingredients. It enables effective load balancing in
                  a parallel environment.",
}

Here is the journal page, and here is a pdf version of the paper.
I hope this can be useful.