Selection algorithms on sorted matrix

Yes, there is an O(K) algorithm due to Frederickson and Johnson.

Greg N. Frederickson and Donald B. Johnson. Generalized Selection and Ranking: Sorted Matrices. SIAM J. Comput. 13, pp. 14-30. http://epubs.siam.org/sicomp/resource/1/smjcat/v13/i1/p14_s1?isAuthorized=no

With the matrix given in the example: If you want to search for the 7-th element, you know the 7-th element is in the elements M[4][1..4], M[1..4][4]. You obtain two arrays already sorted, 12,14,15,20 and 11,17,19 which can be merged. Then you apply a binary search which is O(log N).

Generalize: for k-th biggest element in this matrix, you have to select the proper layer: [2N-1] + [2(N-1)-1]+...>=k so the algorithm to select the proper layer to lookout for is Sum[2(N-i)-1]>=k, for i=0,N-1, where i is the layer's number. After you find i, the layer number, you will have 2(N-i)-1 elements in that array that have to be merged and then searched. The complexity to search that layer is O(log[2(N-i)-1] = O(log(N-i))...

The arithmetic progression leads to

0>=i^2-2*N*i+k

i1,2=N+-sqrt(N^2-k), where k is the element we search...