Sorting optimization to presorted array

Question

I'm looking up the complexities of sorting algorithms. There can be performance harm when the array is already presorted when running certain algorithms. E.g. Using last element as pivot in quick sort would harm the performance when the array has already been pre-sorted. However, when I attempt to cross check with other sources for ways to walk around it, it seems there's no source suggesting putting in place a check to see if the array has already been sorted is one way to walk around, despite the simplicity of this solution.

So I wonder is it practically feasible? If so, why people are not implementing this on every sorting algorithms just before they begin to check if the array has already been presorted before the sorting algorithm executes? Especially when such checking only involve O(n) time at max.

Answer 1

I think what you have read are the implementations of most sorting algorithm in their basic form, which focuses mainly on the idea of how they sort elements. This makes them easy to teach, understand, and analyze. But they can be improved and modified. One sorting algorithm, which is being used in practice, with the kind of optimization you are thinking of is Timsort, which is based from mergesort and insertion sort.

Another fairly recent sorting algorithm that takes advantage of data having presorted runs is Quadsort.