Quicksort is an O(nlog(n)) sorting algorithm. Does this mean it will always be faster than an insertion sort which is an O(n2) algorithm? Why/Why not?

CodePudding user response：

In extreme cases, both quicksort and insertion sort can actually have the same performance of O(n). For an insertion sort of a collection which is already sorted, inserting a new element would take at most O(n) comparisons and also would require just O(1) for the insertion. The worst case behavior of quicksort happens when the partitioning always results in one element followed by the rest of the collection. If this continues all the way down the tree, then quicksort in this worst case can also run in O(n).

However, in the general case, we expect that quicksort will perform as O(n*lgn) and insertion sort will perform as O(n^2).

CodePudding user response：

Depending on the system, for small arrays with 16 to 96 elements, insertion sort can be faster. Visual Studio switches from quicksort or merge sort to insertion sort for <= 32 elements.