Does List<T>.Sort suffer worst case performance on sorted lists?

Question

According to the docs List<T>.Sort uses the QuickSort algorithm. I've heard that this can exibit worst case performance when called on a pre-sorted list if the pivot is not chosen wisely.

Does the .NET implementation of QuickSort experience worst case behaviour on pre-sorted lists?

In my case I'm writing a method that's going to do some processing on a list. The list needs to be sorted in order for the method to work. In most usage cases the list will be passed already sorted, but it's not impossible that there will be some small changes to the order. I'm wondering whether it's a good idea to re-sort the list on every method call. Clearly though, I am falling into the premature optimization trap.

Answer 1

Edit: I've edited the question.

My question was badly asked I guess. It should really have been:

Does List<T>.Sort suffer worst case performance on sorted lists?

To which the answer appears to be "No".

I did some testing and it seems that sorted lists require fewer comparisons to sort than randomized lists: 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

Of course, @dlev raises a valid point. I should never have allowed myself to get into a situation where I was not sure whether my list was sorted.

I've switched to using a SortedList instead to avoid this issue.