Self Doubt

Question

What is adaptive algorithm and is merge sort and quick sort is adaptive?

Answer 1

Adaptive by definition means acting according to the situation.

So, in terms of sorting, if the input array is already sorted to only few elements are misplaced, then if the algorithm sorts it in its best case time, it is said to be adaptive.

Neither quick sort nor merge sort is adaptive. (Can easily be understood by their algorithms).

Comments

But in the solution of ACE given that quick sort is adaptive.

---

Quick sort takes O(n²) on a sorted array. That's the worst case, so it is surely not adaptive. May be wrong solution. 

---

quick sort is not adaptive

 go through thishttps://www.itu.dk/~pagh/CAOS/Fagerberg.pdf