CODEWITHSUNDEEP
c#performancequicksort
RichardTowers
RichardTowers

Reputation: 4762

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

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.

Upvotes: 3

Views: 2630

Answers (3)

RichardTowers
RichardTowers

Reputation: 4762

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.

Upvotes: 5

Ben Voigt
Ben Voigt

Reputation: 283634

Choosing the right algorithm is not premature optimization.

When your list is already sorted or nearly so, it makes sense to use a stable sort. .NET ships with one, LINQ's OrderBy implementation. Unfortunately, it will copy your entire list several times, but copying is still O(N), so for a non-trivial list, that will still be faster.

Upvotes: 3

Josh
Josh

Reputation: 10604

Until you have hard metrics to make comparisons off of, you would be falling into the premature optimization trap. Run your code in a loop over 1000 times and gather time for execution using the two different methods to see which is faster and whether it makes a difference.

Upvotes: 2

Related Questions