Cache-Oblivious Selection in Sorted X+Y Matrices

Mark de Berg, Shripad Thite

Let X[0..n-1] and Y[0..m-1] be two sorted arrays, and define the mxn matrix A by A[j][i]=X[i]+Y[j]. Frederickson and Johnson gave an efficient algorithm for selecting the k-th smal…