快速排序是一种O(nlog(n))排序算法。这是否意味着它总是比插入排序快而插入排序是一个O(n2)算法?为什么/为什么不?
在极端情况下，快速排序和插入排序实际上都具有与O(n)相同的性能。对于已经排序的集合进行插入排序，插入新元素最多需要O(n)比较，并且插入只需要O(1)。快速排序的最坏情况是，分区总是导致一个元素后面跟着集合的其余部分。如果这种情况一直持续下去，那么在这种最坏情况下的快速排序也可以在O(n)中运行。
然而，在一般情况下，我们期望快速排序将执行O(n*lgn)，插入排序将执行O(n^2)。
根据系统的不同，对于包含16到96个元素的小数组，插入排序可以更快。对于<= 32个元素，Visual Studio从快速排序或归并排序切换到插入排序。