efficient algo for nearly sorted array

Question

25. The algorithm that will efficiently sort an array that is nearly sorted except for the interchange of some adjacent pairs of numbers like : $\{1,3,2,5,4,6\}$ is :
A. Quick sort
C. Merge sort
B. Bubble sort
D. Selection sort

Answer 1

infact insertion sort can do it in O(n) time i think.. all others will take relativvely more time.

Comments

@anusha still n-1 passes will be done and comparison will be done each time.

I tihnk answer should be Insertion short but not in option.

And if we go by option then out of all merge sort is better

---

yeah i was editing it.. i too think the same

---

Make C) as the answrr

---

Bubble sort should be the answer. Look at the statement:

Adjacent numbers are interchanged

 Perfect for bubble sort . 1 pass - O(n)

---

ya exactly...Bubble sort will do in single pass