Is the Sorting Algorithm Used by .Net's 'Array.Sort()' Method a Stable Algorithm

Is the sorting algorithm used by .NET's `Array.Sort()` method a stable algorithm?

From MSDN:

This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

The sort uses introspective sort. (Quicksort in version 4.0 and earlier of the .NET framework).

If you need a stable sort, you can use Enumerable.OrderBy.

Which sorting algorithm is used by .NET's Array.Sort() method?

It uses the QuickSort algorithm.

Source:

• Array.Sort Method _{(MSDN, Remarks section)}

What sorting algorithm does the .NET framework implement

There are two biggies.

Array.Sort (which sorts an array in-place) uses an unstable Quicksort.

This is the same implementation used internally by List<T>.Sort, according to the MSDN documentation:

This method uses Array.Sort, which
uses the QuickSort algorithm.

The Enumerable.OrderBy<TSource, TKey> method (which sorts a copy of an input sequence) uses a stable Quicksort.

As far as I know, these are the only two sorting implementations in the .NET BCL.

how was Array.Sort implemented in .NET?

Array.Sort is an unstable sort, so the order of elements which are the same is undefined and not conserved. The article on Array.Sort in MSDN states:

This method uses the QuickSort algorithm. This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

LINQ's OrderBy methods on the other hand are stable. The article on OrderBy in the MSDN states:

This method performs a stable sort; that is, if the keys of two elements are equal, the order of the elements is preserved. In contrast, an unstable sort does not preserve the order of elements that have the same key.

What Sorting Algorithm Is Used By LINQ OrderBy?

For LINQ to Objects, it's a stable quicksort that is used. For any other kind of LINQ, it's left to the underlying implementation.

ArrayList.Sort should be a stable sort with an IComparer but is not?

What the documentation appears to be saying is that the only way you can get a stable sort with ArrayList.Sort is to use an IComparer that somehow 'knows' the indices of the items that are being compared (one would imagine accomplishing this by making it run an initial pass on the collection) and uses that information as a tie-breaker for otherwise equal elements.

Although I agree that the phrasing of the documentation leaves much to be desired, it really doesn't make sense that any old comparer that doesn't consider the indices of the items to be compared can magically turn an inherently unstable sorting algorithm (which is what Arraylist.Sort is) into a stable one.

Does ListT.Sort suffer worst case performance on sorted lists?

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.

---

Related Topics