40 views
If the number of records to be sorted is small, then ...... sorting can be efficient.
A. Merge B. Heap
C. Insertion D. Bubble

And why?
| 40 views
+1
Insertion because of high probability they number of inversion pairs well be less so majority of times it will take O(n)
0
but if given array is totally reverse then complexity will be o(n2) of insertion sort

Array to be sort : 9 8 7 6 5 4 3 2 1

Sorted Array: 1 2 3 4 5 6 7 8 9
0
Exactly, this is where my confusion lies..
+1
So you have considered 9 elements what is probability that that will be in reverse position 1/9!

How many cases are there when no element is in its right position and compare it with 1 elements in its right position , 2 elements in right position , 3 in right and so on

Probability is very low

Consider this 123

123

132

213

231

312

321

No element in its right position 2/6 atleast one in right position 4/6

So number of elements in its correct position will affect inversion pair

In short worst case is O(n$^{2}$) but probability that worst case will happen is less
0
Okay..got it, thanks.