How to get the optimized quicksort algorithm's time complexity

Question

I learned in my data structures class that QuickSort can be optimized by calling the InsertionSort method when the length of the subarray is less than a certain threshold. However, when it comes to the actual time complexity calculation of the optimized version of QuickSort, I'm having trouble finding the result. The problem is as follows.

An optimized-QuickSort function calls the InsertionSort method instead of itself when the size of the sublist is less than k. Assuming that the time complexity of QuickSort and InsertionSort is $c_1n\log n$, $c_2n^2$ respectively, what is the time complexity of optimized-QuickSort? (Calculate for the average case)

I assumed that the sublist is split into 1:1 by each step. As a result, I got $c_1nlog$($n\over k$) + $c_2nk$, but I am definitely not sure of my answer since I don't know if my assumption is correct. In the textbook, the average case of a non-optimized QuickSort was supposed to be calculated by assuming the partition could be the first element, second element, third element, ... , last element and then dividing the whole sum by n.

I would appreciate some help! Thanks.

Answer 1

The height of tree is not $log(\frac{k}{n})$ which is negative because $k<n$. We stop expanding the tree when we reach $k$, therefore we reduce the height of the original tree by $log(k)$. So the height is $log(n)-log(k)=log(\frac{n}{k})$ and the average running time will be: $$c_1nlog(\frac{n}{k})+c_2nk=c_1nlogn-c_1nlogk+c_2nk$$ As noted in comments, since $k$ is constant, that is equivalent to $\theta(nlogn)$.

EDIT: I just noted that the problem was about average case complexity and you assumed the partition to have 1:1 ratio, which is the assumption for best case scenario. For average case analysis, we shouldn't consider any fixed partition ratio.

You can use the average case analysis in section 7.4.2 of CLRS book; except that here the probability of comparing the ith and jth element would be at most $\frac{1}{j-i+1}$, so the $c_1nlogn$ would be an upper bound on the Quicksort part of the average case. As for Insertion sort part, there would be at most $n/k$ leaves with size $k$, with total cost of $\frac{n}{k}c_2k^2=c_2nk$.

Answer 2

For fixed k, and n ≤ k, O(n) is meaningless. O(n) requires arbitrary large values n. With a fixed k, sorting n ≤ k items with InsertionSort takes O(1) - but with a large constant if k is large. Here's what you do to find the best k:

Iterate for k = 2, 3, 4, 5 ... (hoping that your algorithm is clever enough not to sort arrays of size 1). Create a million or a billion arrays of size k filled with random array elements. Measure how long it takes to sort these arrays using InsertionSort, or another method that you like, and how long it takes to sort these arrays doing one partition step, then sorting both halves with InsertionSort.

Make sure that you don't switch between both methods for each array, because looking at the same data repeatedly will cache the data, and the second operation will tend to be faster.

If your array doesn't contain primitive data but objects with constructors and destructors, you can save a lot more time by reducing the number of assignments. Selection sort will tend to be faster in that case than InsertionSort because it does fewer expensive assignments.