- Naive sort
`O(n^2 logn)`

Sort the whole matrix and find the kth. - Merge rows (or columns)
`O(n^2)`

`O(n^2 logn)`

Merge the rows and find the kth. - Heap
`O(k logn)`

*ActuallyI think it's*`O(n^2 logn)`

since k=O(n^2)

See geeksforgeeks.

~~If k is guaranteed to be small, that the last one is definitely better. However In my opinion, generally the second solution is better. Do I understand it correctly?~~