In certain sorting problems, if the data is already sorted the complexity of the sorting algorithm changes. That is it can be said that the time complexity depends on the order of a given input.Â
Based on the dependency of time complexity on the arrangement of array, the sorting algorithms can be divided into two groups:
- Adaptive Sorting Algorithms
- Non-adaptive Sorting Algorithms
Adaptive Sorting Algorithms:
The sorting algorithms in which the order of elements affects the time complexity of the sorting algorithm is known as an adaptive sorting algorithm.
In adaptive sorting, if the data is already sorted, the algorithm will not reorder the elements. As a result, it reduces the number of iterations and improves execution speed.
Here is a list of sorting algorithms that are adaptative :
In the case of adaptive sorting algorithms, if the array is already sorted it takes linear time to perform sorting i.e., O(N) time.
Advantages of Adaptive Sorting Algorithms:
- When the data is already sorted, it consumes less time.Â
- They generally load faster.
- Improved execution speed.
Non-Adaptive Sorting Algorithms:
The sorting algorithms in which the order of elements of the data doesn’t affect the time complexity of the sorting algorithms are known as non-adaptive sorting algorithms.
In a non-adaptative algorithm, the time complexity remains the same for any order of the array. A non-adaptive sorting algorithm tries to force all the items into sorted order.
Here is a list of Non-Adaptive sorting algorithms:
Advantages of non-adaptive sorting algorithms:
In case of non-adaptive sorting, the time complexity remains unaffected by the order of elements. This helps in situations when the order of elements are cannot be guessed or are not known beforehand. In such cases algorithms like merge sort or heap sort run with their usual complexity of O(N * logN) which is faster than many others in worst case.