Are closely related sorting algorithms Radix Sort and Bucket Sort Adaptive?
I know that a sorting algorithm is said to be adaptive if data to be sorted is pre-sorted and the algorithm takes minimal time.
However I am unable to conclude whether Radix and Bucket sort algorithms are adaptive or not.
A sorting algorithm falls into the adaptive sort family if, it takes advantage of existing order in its input.
For example, "Insertion sort" is an adaptive sorting algorithm, if input is already sorted then time complexity will be O(n).
In case of "Bucket sort(or Bin sort)" and "Radix sort", there's no advantage for input order. Time complexity doesn't vary based on input order. That's why they are not adaptive sorting algorithm.
Note: To understand whether a sorting algorithm falls into adaptive sort family, you've to think about implementation approach, by which it's possible to optimize time complexity based on input order. Adaptive sorting is usually performed by modifying existing sorting algorithms.
Hope, it helps!
Resources: