algorithm - Sorting and Selecting an almost sorted array -

given array of length n each item has distance of @ log(n) final position in sorted array, how efficiently sort it, , how find k-th valued item (select-k)?

this starting ideas:

for sorting, using comparison model can there approximately o((logn)^n) possible permutations, therefore max-depth of comparison tree should o(nloglogn). also, select problem, have intuition if @ range of logn each side of k-th item (2logn - 1), can use deterministic selection algorithm in o(logn), i'm not sure how prove correctness of method.

please note i'm not looking code (in language), sketch of abstract algorithm , time complexity it.

thanks.

use minheap of length

x=log(n) 

start beginning , push elements heap , accordingly after x insertions find smallest element , continue on scan other elements.

complexity -

o(n(log(x))) = x*log(x)(for heap operations first x elements) + (n-x)(log (x))(for remaining elements) x=log(n); 

you can identify k-th value on way sorting keeping track of how many elements have sorted......