Which sorting algorithm is known to be adaptive?

The concept of an adaptive sorting algorithm refers to the ability of the algorithm to take advantage of existing order in a dataset. This means that if the data is already partially sorted, an adaptive algorithm can perform better than its worst-case time complexity.

Insertion sort is recognized as an adaptive sorting algorithm because it efficiently sorts a list that is already partially sorted. When elements are in order, the algorithm requires fewer comparisons and movements, which allows it to finish in linear time, O(n), in the best case scenario. This contrasts with its worst-case time complexity of O(n²) when the data is in reverse order.

In contrast, algorithms like bubble sort and selection sort are not adaptive because they have a consistent performance regardless of the initial condition of the data. Mergesort, while efficient, is not considered adaptive as it divides the data for sorting and does not adjust based on existing order within the dataset. Therefore, insertion sort stands out as the correct choice for the question regarding which sorting algorithm is adaptive.