List<T>.Sort 在排序列表上的性能最差吗？

Question

根据文档 List<T>.Sort使用 QuickSort 算法。我听说如果没有明智地选择枢轴，在预先排序的列表上调用时，这可能会表现出最坏情况的性能。

QuickSort 的 .NET 实现是否在预排序列表上遇到最坏的情况？

在我的情况下，我正在编写一个方法来对列表进行一些处理。需要对列表进行排序才能使该方法起作用。在大多数使用情况下，列表将通过已经排序的，但对顺序进行一些小的更改并非不可能。我想知道对每个方法调用重新排序列表是否是一个好主意。很明显，我陷入了过早的优化陷阱。

Answer 1

编辑：我已经编辑了问题。

我猜我的问题问得不好。真的应该是：

List<T>.Sort在排序列表上是否遭受最坏情况的性能？

答案似乎是“否”。

我做了一些测试，似乎排序列表需要比随机列表更少的比较来排序：https : //gist.github.com/3749646

const int listSize = 1000;
const int sampleSize = 10000;

var sortedList = Enumerable.Range(0,listSize).ToList();
var unsortedList = new List<int>(sortedList);

var sortedCount = 0;
sortedList.Sort((l,r) => {sortedCount++; return l - r;});
//sortedCount.Dump("Sorted");
// Returns: 10519   

var totalUnsortedComparisons = 0;
for(var i = 0; i < sampleSize; i++)
{
    var unsortedCount = 0;
    unsortedList.Shuffle();
    unsortedList.Sort((l,r) => {unsortedCount++; return l - r;});
    totalUnsortedComparisons += unsortedCount;
}

//(totalUnsortedComparisons / sampleSize).Dump("Unsorted");
// Returns: 13547

当然，@dlev 提出了一个有效的观点。我不应该让自己陷入不确定我的列表是否已排序的情况。

我已经改用SortedList来避免这个问题。