CareerCup

Insertion sort works in linear time....because in the worst case if the 50 unsorted numbers are at the end of the array..then array would have to be shifted approx 50n times..and if 50<<<n..it can be neglected..hence linear time///

a form of merge sort is better.
it can be done in O(n+m*log(m)), which is significantly better then O(n*m) or O(n*log(n)):

1. run over the array, O(n)
1.1. every time encountering unsorted element, move it to array2 (array size will be m).
1.2. since you get gaps, move each sorted element k cells back (where k is the number of dislocated elements), which will leave m empty cells in the end of the array.
2. sort array2 in O(m*log(m))
3. merge sort the two sorted arrays from end to start (for each element choose the better and put it in the end of array1). O(m+n)

any idea how to solve this question

i think insertion sort will work here..as insertion sort works really well on partially sorted arrays

In my opinion insertion sort is the best way to get this done. any thoughts?

yes insertion sort is the best

My first thought was indeed Insertion sort...
But for every displaced number you insert, you'd have to 'shift' the entire sub-array that is larger than the displaced number.
Obviously smells like O(m.n) solution at 'best', n being total numbers (100000), m being displaced numbers (50).
Can't we do better than that, like O(n)?

--- I guess NOT LOL...

I agree, Insertion sort should be the expected answer~

For 1000 elements, quick sort is also considered because it might reduce swapping elements overhead in selection sort, but it takes more space.

Merge sort scales well to very large lists. Its complexity for sorting the data is o(nlogn) whereas in case of insertion sort the worst case complexity is o(n^2)...

insertion sort is the answer, the order is O(n+d), d number of inversions, in this case 50, so it's order O(n).

I think merge sort is the right answer.

Insertion sort is the correct ans.it will require very small number of swap operation (which will be equal to number of inversion) that we can neglect. We will achieve Time complexity almost O(n).
and space O(1)..

I don't think insertion sort is a good idea. for example, if the array is ascending, and we have several big displaced number at the beginning of the array, how to handle it?
I think the heap sort would be fast, because the heap is almost built.

Why do you even have to use one of the 'standard' sorting algoirthms?

no to insertion sort since O(n^2) is the time complexity.

no to merge sort since given elements of array , it takes space comp. of O(n)

i feel... heap sort O(nlogn)is the best choice with the input arrays itself is used to store data.

cook-kim algorithm?

Quikcksort is the best. This is also called partition exchange sort. The objective of partition is to allow a specific element to find its proper position with respect to others in the sub array.
Quicksort is fastest with low overhead and its average O(n log n) behavior.