How is Array.Sort implemented in .NET?

Question

I use structures in my programming, and I sort the structure according to the value in the structure using IComparer .

How does Microsoft implement the Array.Sort() method? Is there any documentation (links) for this? Is this the same for all types of Sort() in Visual Basic?

This is a simple example of what I want.

 Dim MyArray(6) As Integer MyArray(0) = 1 MyArray(1) = 45 MyArray(2) = 45 ' Some Code..... '......... '.......... MyArray(3) = 1 MyArray(4) = 10 ' Some Code..... '......... '.......... MyArray(5) = 1 MyArray(6) = 57 Array.Sort(MyArray) 

Array.Sort() will sort this array as: (1 1 1 10 45 45 57)

How to sort number 1? Is it bringing to the end of the first or keeping the old in the same index?

In my original example (before sorting), MyArray(0) = 1 and after sorting MyArray(0) = 1 .

Is this the same original 1 or this other 1 (new, added to the array), moved to this position?

If sorting MyArray(0) = 1 after sorting should be MyArray(5) = 1 before sorting.

Answer 1

Array.Sort is an unstable sort, so the order of elements that are the same is undefined and is not preserved. The MSDN article Array.Sort states:

This method uses the QuickSort algorithm. This implementation performs unstable sorting; that is, if two elements are equal, their order may not be preserved. In contrast, robust sorting preserves the order of equal elements.

LINQ OrderBy methods, on the other hand, are stable. The MSDN OrderBy article states:

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

Answer 2

It uses the Quicksort algorithm, which is unstable when deployed efficiently (in place). This means that it does not guarantee that equal values ​​retain their previous relative position after sorting.

For example, if you have a bunch of dots:

 Point[] points = new Point[] { new Point(0, 1), new Point(0, 2), new Point(0, 3), new Point(1, 1), new Point(1, 2), new Point(1, 3) }; 

And you only sort these points by the x coordinate using this comparator:

 private int CompareByX(Point a, Point b) { return aX - bX; } 

This only guarantees that the points are sorted by their x coordinate, that is, you can easily get a mixed order (when viewing the y-coordinate):

 Point(0, 3) Point(0, 2) Point(0, 1) Point(1, 3) Point(1, 2) Point(1, 1) 

[change]

This does not mean that the sorting algorithm is not deterministic (random). For the same input, you get the same output for each run. You can also predict exactly how it will be reorganized if you study the algorithm exactly, but it is not necessary. Just know that this happens when using the sorting procedure.

Here is a working example of your problem, try resizing the test data (first line in Main ) and see how the array is reorganized in each run:

 class Program { static void Main() { Point[] points = CreateTestData(1, 4).ToArray(); DisplayItems("Before", points); Array.Sort(points, CompareByX); DisplayItems("After", points); Console.ReadLine(); } private class Point { public int X { get; private set; } public int Y { get; private set; } public override string ToString() { return string.Format("({0},{1})", X, Y); } public Point(int x, int y) { X = x; Y = y; } } private static int CompareByX(Point a, Point b) { return aX - bX; } private static IEnumerable<Point> CreateTestData(int maxX, int maxY) { for (int x = 0; x <= 1; x++) for (int y = 0; y <= 4; y++) yield return new Point(x, y); } private static void DisplayItems(string msg, Point[] points) { Console.WriteLine(msg); foreach (Point p in points) Console.WriteLine(p.ToString()); Console.WriteLine(); } } 

Of course, if you expand the delegate comparator to include the Y coordinate, you will not have this problem:

  private static int CompareByX(Point a, Point b) { if (aX == bX) return aY - bY; else return aX - bX; } 

Answer 3

Use .NET Reflector and see for yourself ... From the names of the methods, it seems that they use the QuickSort algorithm: System.Array + SorterObjectArray.QuickSort

Answer 4

Array.Sort (), like most built-in sorters, uses the QuickSort implementation in a helper class behind the scenes. The variety is relatively efficient and is configured using the IComparable and IComparer interfaces, but it is unstable; the three 1s in your example may appear in a different relative order than they were before sorting. You can see this if using a more complex structure:

 struct TestStruct { int a; int b; } ... //As declared, this array is already sorted by both "a" and "b" properties var myStructAray = new [] {new TestStruct{a=1,b=1}, new TestStruct{a=1,b=2}, new TestStruct{a=1,b=3}); //QuickSorts myStructArray based on the comparison of the lambda for each element var newArray = Array.Sort(myStructArray, x=>xa); //newArray may have a different order as myStructArray at this time for(var i=0;i<myStructArray.Count();i++) { //NUnit assertion; will almost surely fail given a sufficient array length Assert.AreEqual(myStructArray[i].b, newArray[i].b); } 

Answer 5

First of all, let me address a few questions in your current plan regarding best practices for .Net (VB or C #):

• Prefers a class over a structure if you have no reason to do so.
• Avoid using arrays
• You can build this array as a single line: Dim MyArray() As Integer = {1, 45, 45, 1, 10, 1, 57}

As for your question about whether this is the “same” value of 1, the answer is that it depends on how you look at it. In general, the answer is whether the sorting algorithm is considered stable ..Net the sorting algorithm is unstable.

In this particular case, you are asking the wrong question. 1 is 1: 1. There is no difference between them. If you think this is important, I urge you to provide a code to detect the difference between any two of the “1s” from this list in your source code (except the array index).