CareerCup

I think the intent here is that, we have 2 methods.

- Sort the rightmost half and merge (in place). Complexity = n + sqrt(n)log(n)
- Use the insertion sort way . Complexity = n*sqrt(n)

So, 1st method is better than 2nd.

Sort the last sqrt(n) and do a merge?

does it need sort in place?

Just wondering what significance sqrt has in the problem. Sorting the rest and merging them would work with any partition of the array.

I think yahoo doesn't want to recruit any more. It seems that they just want to continue interview processes just like that. And they seem to ask really weird questions. Recently a friend of mine faced really weird questions in a yahoo interview.

start insertion sort from n - sqrt(n) pos.. complexity would be n*sqrt(n)

take the last sqrt(n) elements and insert them into the n-sqrt(n) using binary search.
time complexity is O(sqrt(n)*logn)

The way the question is framed I would use insertion sort. Its in place and is suitable for nearly sorted input. The array is arranged such that I can skip the first n - sqrt(n) iterations of the algorithm. The complexity would be O(n * sqrt(n)).

Most of the elements are already sorted in this array. If n = 25, then sqrt(n) = 5. So the problem already has n-sqrt(n) = 25 - 5 = 20 elements in the array sorted. Inserting sort would be a good idea here since it works well for nearly sorted input. Time complexity = O(n * sqrt(n))

I will go with sort the sqrt(n) elements and then merge the elements with n-sqrt(n) elements

insertion sort can also be used

The complexity is O(n) in the worst case. As given, the n - sqrt(n) elements are sorted. Let's assume (a) we are doing insertion sort and (b) the sqrt(n) elements are the smallest sqrt(n) elements in the entire array. In such a case, each insertion requires shifting of O(n-sqrt(n)) elements. Therefore, the total time to sort would be O (sqrt(n) * (n - sqrt(n) ) ) = O(n).

Using Insertion Sort: As maximum of the elements of the array (n - sqrt(n)) are already sorted and only sqrt(n) elements are not sorted, so for a large amount of input, insertion sort would be better. Complexity of the algorithm: O(n * sqrt(n)).

Using Binary Search and Insertion: Suppose an array of 25 elements looks like: 6,7,8,9,10, ....., 25, 5,4,3,2,1. It is the case for the worst case. Just consider the time needed to properly place the last element 1. When it's the turn to insert 1, all other elements are already sorted. So do a binary search on all the (n-1) elements in time log(n-1). Now 1 must be inserted at the front of the array. This insertin needs all the (n-1) elements to move in the right direction. Time complexity: O(n-1). So for a single element to insert properly, the time complexity is: O(n-1) + O(log(n-1)). So for sqrt(n) number of elements this is: O(sqrt(n) * (O(n-1) + O(log(n-1)))). or simply: O(sqrt(n) * n).

It depends on the case which method to use.