Multiple column sorting and arraging algorithm Problem

The goal is to perform the following transformation:



Additionally, if two rows can be merged, they are combined into one:



Code

I wrote the following algorithm to solve this problem:

#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;algorithm&gt;

using Matrix = std::vector&lt;std::vector&lt;int&gt;&gt;;
using Column = std::vector&lt;int&gt;;

Column max_col(const Matrix &amp;v) {
    return *std::max_element(v.begin(), v.end(),
                             [](auto&amp; lhs, auto&amp; rhs)
                             {
                                 return lhs.size() &lt; rhs.size();
                             });
}

bool is_element_in_next_rows(const Matrix &amp;v, int element,int row) {
    for (auto&amp; col : v) {
        if (row &gt;= static_cast&lt;int&gt;(col.size())) continue; // out of range
        if (std::lower_bound(col.begin()+row+1,col.end(),element) != 
            std::upper_bound(col.begin()+row+1,col.end(),element)) {
            return true;
        }
    }
    return false;
}

int min_element_in_row(const Matrix &amp;v, int row) { 
    int min_element = max_col(v)[row];
    for (auto&amp; col : v) {
        if (row &gt;= static_cast&lt;int&gt;(col.size())) continue; // out of range
        if (col[row] != 0) min_element = std::min(min_element, col[row]);
    }
    return min_element;
}

void print_elements(const Matrix &amp;v) {
    for (auto&amp; i : v) {
        for (auto&amp; j : i) {
            std::cout &lt;&lt; j &lt;&lt; " ";
        }
        std::cout &lt;&lt; std::endl;
    }
}

void organize_elements(Matrix &amp;v) {
    for (auto&amp; col : v) {
        std::sort(col.begin(),col.end());
    }
    auto current_max_col = max_col(v);
    for (int row{0}; current_max_col.begin()+row!=current_max_col.end(); ++row) {
        int min_element = min_element_in_row(v,row);
        for(auto&amp; col : v) {
            if (row &gt;= static_cast&lt;int&gt;(col.size())) continue; // out of range
            int candidate = col[row];
            if (candidate &gt; min_element) {
                if (is_element_in_next_rows(v,candidate,row)) {
                    col.push_back(0);
                    std::rotate(col.begin()+row,col.end()-1,col.end());
                }
            }
        }
        current_max_col = max_col(v);
    }
}

int main() {

    Column c1 = {5,6,8,11};
    Column c2 = {2,5,3,1,4,6};
    Column c3 = {8,7,2,4,5,3,1};

    Matrix v;
    v.push_back(c1);
    v.push_back(c2);
    v.push_back(c3);

    std::cout &lt;&lt; "original: \n";
    print_elements(v);
    organize_elements(v);
    std::cout &lt;&lt; "organized: \n";
    print_elements(v);
    return 0;
}


Which produces the following output:

original: 
5 6 8 11 
2 5 3 1 4 6 
8 7 2 4 5 3 1 
organized: 
0 0 0 0 5 6 8 11 
1 2 3 4 5 6 
1 2 3 4 5 7 8 


Questions

I particularly don't like this part of my code: 

auto current_max_col = max_col(v);
for (int row{0}; current_max_col.begin()+row!=current_max_col.end(); ++row) {
    // ....
    current_max_col = max_col(v);
}


I also don't like that I have to do this cast:

if (row &gt;= static_cast&lt;int&gt;(col.size())) continue; // out of range


Is there a way to do this check better?

The fact that I need to declare current_max_col out of the for, and then update it inside the loop. Any idea how to avoid this? 

Any other ideas about how to solve this problem? Any other tips? Thank you!
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.