Geek asks and answers

In an array of n elements, the first n- (root) n elements are sorted first, we must sort the array

We gave an array of n integers, of which the first n- (squareroot) n elements are sorted (this means that the (root) n elements from the last are not sorted). We must sort the entire array with minimal complexity. What could be the difficulty? And what will be our approach? When I tried to solve it, my difficulty is O (n), first sort the remaining array and merge it. Is there any algorithm for solving it with less than O (n)?

+3
source share
1 answer

If your "array" is actually a skip-list , this can be done inO(log(n)sqrt(n))

for each element x in reminder:
   remove x from skip list   (O(1))
   find first element smaller then x in sorted part   (O(logn))
   insert x to the found position    (O(1))

complexity will be sqrt(n)*log(n)

, , ( , ), O(n), , O(n)

+4

More articles:


All Articles