I want to design a new sort algorithm that combines the best of quicksort and insertion sort. At the begining I dont know if my the array is sorted or not. So, I need to choose an efficient one between quicksort and insertion to start. I will choose quicksort. How can I decide during the execution if it is bettwer to switch from quick-sort to insertion sort? So, I think I need to add almost the same code in my new sort algorithm of quicksort and I need to add a new base case. This relation I think should reflect the relation between length of the input array and the recursion depth that hold for a well behaving quick-sort.
So since, the max tree depth (recursion) in quick sort is n and the min is logn, is it is correct my thinking to add the new base case as:
if len(less_than_pivot) == (n-1) :
return insertion_sort(less_than_pivot)
elif len(greater_than_pivot)== n-1:
return insertion_sort(greater_than_pivot)
less_than_pivot means the array including all the elements less than the pivot (same for greater_than_pivot) .
so in principle, i need for the hybrid sorting algorithm, consider the points where quicksort's performance might degrade (e.g., nearly sorted arrays) and switch to insertion sort accordingly.