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

algorithm, arrays, c, sorting

Solution

If your "array" is actually a skip-list, it can be done in `O(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)`

Note that if the data is an actual array, you will need to shift all elements to the right for a single change (if one of the elements in the reminder is the smallest, for example) - and this is done alone in `O(n)`, so for an array you cannot go better then `O(n)`

Problem

We have given an array of n integers of which first n-(squareroot)n elements are sorted (it means (root)n elements from the last are not sorted). We have to sort the entire array with minimum time complexity. What can be the complexity? And what would be our approach? When I tried to solve it, my complexity is O(n) by first sort the remaining array and merge it. Is there any algorithm to solve it with less than O(n)?

Original source