Time complexity of QuickSort+Insertion sort hybrid algorithm?

Question

I am implementing an algorithm that perform Quick sort with Leftmost pivot selection up to a certain limit and when the list of arrays becomes almost sorted, I will use Insertion sort to sort those elements.

For left most pivot selection,I know the Average case complexity of Quick sort is O(nlogn) and worst case complexity ,i.e. when the list is almost sorted, is O(n^2). On the other hand, Insertion sort is very efficient on almost sorted list of elements with a complexity is O(n). SO I think the complexity of this hybrid algorithm should be O(n). Am I correct?

Hello Mr.Rob. No this is not a Homework of mine. I am planning to create my own sorting algorithm that I am going to use in my research work. But i am not very good at complexities. So i needed to know if I am the right direction or do i have to think over it again. I do not need a exact answer but a little help. — user1031752
Can you elaborate how you're choosing your pivot preferably with code? When you say left-most pivot do you mean choosing the first element every time? — greatwolf
Yes. Each time it will choose the left most element as the pivot. After a certain limit when the sub arrays are smaller and almost sorted, the algorithm will finish off with Insertion sort. I think for such an algorithm the complexities will be as follow Best case: O(nlogn) average case O(nlogn) and worst case O(n) — user1031752
You realize O(nlogn) > O(n)? You can't have a worse case that performs better than the average case by definition. — greatwolf

greatwolf greatwolf · Accepted Answer · 2011-11-06T21:04:46

The most important thing for the performance of qsort is picking a good pivot above all. This means choosing an element that's as close to the average of the elements you're sorting as possible.

The worse case of O(n²) in qsort comes about from consistently choosing 'bad' pivots every time for each partition pass. This causes the partitions to be extremely lopsided rather than balanced eg. 1 : n-1 element partition ratio.

I don't see how adding insertion sort into the mix as you've describe would help or mitigate this problem.

Time complexity of QuickSort+Insertion sort hybrid algorithm?

1 Answers