Multiple column sorting and arraging algorithm
It seems that the transform you are after is a k-way merge in disguise.

In the nutshell, set up a min-heap of pairs &lt;col_id, vector&lt;int&gt;::iterator&gt;. On each iteration construct a vector of values equal to heap head, 0 otherwise; push it to the resulting matrix; remove those entries from heap an pull new values from the respective columns. Sorry if I miss something obvious.

I don't think you shall strive for in-place transform.



I am pretty sure that merging rows deserve a separate pass.



The

                col.push_back(0);
                std::rotate(col.begin()+row,col.end()-1,col.end());


is no better than col.insert(col.begin() + row, 0);



The static_cast&lt;int&gt;(col.size()) suggests that row should not be int, but along the lines of std::vector&lt;int&gt;::size_type.