How to efficiently insert into 2-D sort matrix with O(n) time

Question

I need to insert into a sorted 2-D n x n matrix, insertion should be achieved in O(n). but the condition is the whole matrix is not sorted, only rows and columns are sorted.

example:

9  10 12 14
11 12 14 15
21 22 28 Null
23 24 Null Null

after inserting a new element into the above matrix the matrix should be sorted in row and column wise.

My approach

I am thinking to do something like inserting the new element at the end of the matrix (3, 3), from there I will check (3, 3-1) and (3-1, 3) I will swap (3, 3) with max[(3, 3-1), (3-1, 3)] if (3, 3) < max[(3, 3-1), (3-1, 3)], like that I will traverse the whole matrix until there is no swapping is required.

Please let me know If there is a better way to do it.