0 votes 0 votes 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? Solarica Palit asked Aug 2, 2018 Solarica Palit 597 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Tesla! commented Aug 2, 2018 reply Follow Share Insertion because of high probability they number of inversion pairs well be less so majority of times it will take O(n) 1 votes 1 votes minex let's go commented Aug 2, 2018 reply Follow Share 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 votes 0 votes Solarica Palit commented Aug 2, 2018 reply Follow Share Exactly, this is where my confusion lies.. 0 votes 0 votes Tesla! commented Aug 3, 2018 reply Follow Share 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 1 votes 1 votes Solarica Palit commented Aug 4, 2018 reply Follow Share Okay..got it, thanks. 0 votes 0 votes Please log in or register to add a comment.