合并排序(nlogn)的效率总是比选择排序(n^2)快。什么时候你会选择选择排序而不是合并排序？
解决方案：
因为选择排序的运行时间是Θ(n2)，而mergesort的运行时间为O(n log n)，对于足够大的输入，mergesort的性能将优于选择排序。然而，在两个方面，选择排序可能会更好。
数组上的选择排序可以用O(1)辅助存储空间来实现，而(大多数)数组上的mergesort实现则使用Θ(n)辅助存储空间。因此，如果内存非常稀缺，选择排序将是比mergesort更好的选择。(然而，它比堆排序或quicksort更糟糕！)
在小的输入数组上，选择排序可能比mergesort更快，因为它是一种更简单的算法，比mergesort所隐藏的常数系数更低。如果你要排序，比如说，16个左右元素的数组，那么选择排序可能会比mergesort快。(然而，它可能会是一个比插入排序更糟糕的选择)。
所以换句话说，在某些情况下，选择排序会比mergesort更好，但在这些情况下，你可能还是使用另一种排序算法更好。)
