Problem 6-3 Young tableau, the insert operation is incorrect.

[ekaradon-Alexander]

CLRS/C06-Heapsort/young.cpp

Line 43 in b7d3df5

void INSERT(vector<vector<int> > &young, int v)

Please test with the following example.

int main() {
    int arr1[4] = {2, 3, 8, 14};
    int arr2[4] = {4, 5, 9, 16};
    int arr3[4] = {12,INT_MAX,INT_MAX,INT_MAX};
    int arr4[4] = {INT_MAX,INT_MAX,INT_MAX,INT_MAX};

    vector<int> v1(arr1, arr1 + 4);
    vector<int> v2(arr2, arr2 + 4);
    vector<int> v3(arr3, arr3 + 4);
    vector<int> v4(arr4, arr4 + 4);
    
    vector<vector<int> > v;
    v.push_back(v1);
    v.push_back(v2);
    v.push_back(v3);
    v.push_back(v4);
    
    INSERT(v, 6);

    print_young(v);

    return 0;
}

The original tableau is

2       3       8       14
4       5       9       16
12     inf     inf     inf
inf    inf     inf     inf

By inserting number 6 to the tableau, the correct result should be

2       3       6        8
4       5       9       14
12     16      inf     inf
inf    inf     inf     inf

But your solution gives

2       3       6        8
4       5       9       14
12     inf     inf      16
inf    inf     inf     inf

Those elements moved downwards to the next row (e.g., the number 14 and 16 in this example) should be placed in a proper position (in its current row) by comparing with other elements in this row. However, introducing this revision results in an algorithm with a complexity of O(m*n), rather than the required O(m+n).

P.S. In fact I doubt that whether these exists an algorithm with complexity O(m+n).