Sort scrambled two-dimensional array filled with numbers by swapping adjacent numbers
Mathematica, not golfed

towards[a_,b_]:={a,a+If[#==0,{0,Sign@Last[b-a]},{#,0}]&amp;@Sign@First[b-a]};
f[m_]:=Block[{m2=Map[QuotientRemainder[#-1,10]+1&amp;,m,{2}]},
  Rule@@@Apply[10(#1-1)+#2&amp;,#,{2}]&amp;@
    Reap[Table[
      m2=NestWhile[
        Function[{x},x/.(Sow[#];Thread[#-&gt;Reverse@#])&amp;[x[[##]]&amp;@@@towards[First@Position[x,i,{2}],i]]]
        ,m2,#~Extract~i!=i&amp;];
      ,{i,Reverse/@Tuples[Range[10],2]}];][[2,1]]]




Explanation:

The algorithm is similar to "bubble sort". These 100 numbers are put into correct order one by one, 1, 11, 21, ..., 91; 2, ..., 92; ...; 10, ..., 100. They are first move up/down to the correct rows, and then move left to the correct columns. 

Function towards gives the two position to swap. For example, if {5,2} is moving to {1,1}, towards[{5,2},{1,1}] gives {{5,2},{5,1}} (move up); and  towards[{5,1},{1,1}] gives {{5,1},{4,1}} (move left).



Results:

For the test case, the total number of swaps is 558. The first few swaps are, 

{1-&gt;76,1-&gt;34,1-&gt;35,1-&gt;88,1-&gt;41,11-&gt;16,11-&gt;69,11-&gt;46, ...


For a random configuration, the total number of swaps is 558.5 ± 28.3 (1σ).