Both quicksort and mergesort have an expected time of O(n log n) to sort a list

Question

Both quicksort and mergesort have an expected time of O(n log n) to sort a list containing n items. However, in the worst case, quicksort can require O(n^2) time, while mergesort’s worst case running time is the same as its expected time,
O(n log n).

(a) What accounts for the difference in worst case times? How is it that quicksort can require O(n^2) time, while mergesort always guarantees O(n log n)?

(b) Given that mergesort’s worst case time is better than quicksort’s, why bother ever to use quicksort at all? (i.e., why is quicksort so commonly used in practice?)

Explanation / Answer

a: Merge sort is a divide and conquer algorithm. Think of it in terms of 3 steps -

1.The divide step computes the midpoint of each of the sub-arrays. Each of this step just takes O(1) time.
2.The conquer step recursively sorts two subarrays of n/2 (for even n) elements each.
3.The merge step merges n elements which takes O(n) time.
Now, for steps 1 and 3 i.e. between O(1) and O(n), O(n) is higher. Let's consider steps 1 and 3 take O(n) time in total. Say it is cn for some constant c.

How many times are these steps executed?

For this, look at the tree below - for each level from top to bottom Level 2 calls merge method on 2 sub-arrays of length n/2 each. The complexity here is 2 * (cn/2) = cn Level 3 calls merge method on 4 sub-arrays of length n/4 each. The complexity here is 4 * (cn/4) = cn and so on ...

Now, the height of this tree is (logn + 1) for a given n. Thus the overall complexity is (logn + 1)*(cn). That is O(nlogn) for the merge sort algorithm.

When quicksort always has the most unbalanced partitions possible, then the original call takes cn cnc, n time for some constant c, the recursive call on n-1, elements takes c(n-1) time, the recursive call on n-2 elements takes c(n-2) time, and so on.

When we total up the partitioning times for each level, we get
cn + c(n-1) + c(n-2) + ... + 2c = c(n + (n-1) + (n-2) + ... + 2) = c((n+1)(n/2) - 1)

The last line is because 1 + 2 + 3 + ... + n is the arithmetic series, as we saw when we analyzed selection sort. (We subtract 1 because for quicksort, the summation starts at 2, not 1.) We have some low-order terms and constant coefficients, but when we use big- notation, we ignore them. In big- notation, quicksort's worst-case running time is (n^2).

b: You shouldn't center only on worst case and only on time complexity. It's more about average than worst, and it's about time and space.

Quicksort:

- has average time complexity of (n log n);
- can be implemented with space complexity of (log n);

Also have in account that big O notation doesn't take in account any constants, but in practice it does make difference if the algorithm is few times faster. (n log n) means, that algorithm executes in K n log(n), where K is constant. Quicksort is the comparison-sort algorithm with the lowest K.

Average asymptotic order of QuickSort is O(nlogn) and it's usually more efficient than heapsort due to smaller constants (tighter loops). In fact, there is a theoretical linear time median selection algorithm that you can use to always find the best pivot, thus resulting a worst case O(nlogn). However, the normal QuickSort is usually faster than this theoretical one.

To make it more sensible, consider the probability that QuickSort will finish in O(n2). It's just 1/n! which means it'll almost never encounter that bad case.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.