.NET Reference Guide

Sorting a Multi-Dimensional Array with LINQ

Last updated Dec 18, 2009.

In Sorting a Multi-Dimensional Array, I showed how to use the IComparer interface to sort multi-dimensional arrays--something that the built-in Array.Sort method can't do. That article was written several years ago, before the introduction of generics and before LINQ. Whereas it's easy enough to modify the example code so that it works with generics, getting LINQ to sort those arrays seems to stump some people.

Sorting a jagged array

As I pointed out in the original article, .NET supports two types of arrays: jagged arrays and rectangular arrays. And although only rectangular arrays are CLR compliant, many .NET programs still use jagged arrays because in many cases they are more efficient and easier to use.

A jagged array is, in essence, an array of arrays. In C#, the declaration is very simple:

// declare and initialize a jagged array
int[][] a = new int[][] 
{
    new int[]{33, 12},
    new int[]{12, 10},
    new int[]{13,5},
    new int[]{27, 19}
};

If there's any doubt about the "array of arrays" characterization, take a look at the corresponding Visual Basic code.

' declare and initialize a jagged array
Dim a1() As Integer = {33, 12}
Dim a2() As Integer = {12, 10}
Dim a3() As Integer = {13, 5}
Dim a4() As Integer = {27, 19}
Dim a()() As Integer = {a1, a2, a3, a4}

I keep thinking that there should be a cleaner way to do that in Visual Basic, but my VB skills are somewhat lacking. In any case, it's clear that this creates an array of arrays.

In the original article, I showed how to sort this array by passing an IComparer to the Array.Sort method. Whereas that option is still available, changes in .NET and in the C# and Visual Basic languages give several other ways to approach the problem.

One way (and probably the simplest) to approach the problem is to call the Array.Sort overload that takes a generic Comparison delegate as a Lambda expression. Doing so turns the sorting into a one-liner. For example, this code sorts the array based on the second item in each of the subarrays:

[C#]

Array.Sort(a, (a1, a2) => { return a1[1].CompareTo(a2[1]); });

That is, the C# code is a one-liner because C# allows anonymous methods. Since Visual Basic doesn't support anonymous methods, you have to create the Lambda expression prior to calling Array.Sort. It's another line of code, but at least it keeps the comparison function right there with the sort call:

[Visual Basic]

Dim sorter As Comparison(Of Integer()) = Function(x() As Integer, y() As Integer) x(1).CompareTo(y(1))
Array.Sort(a, sorter)

Given the above code that uses a Comparison delegate, the syntax to make LINQ sort the array just falls into place:

[C#]

var sorted = from x in a
             orderby x[1]
             select x;

[Visual Basic]

Dim sorted = From x In a _
             Order By x(1) _
             Select x

The result of the LINQ sort is somewhat different from what you'd expect. First of all, it does not sort the array in place. The source array is left in its original condition. In addition, the sorted object is not an array. At least, it can't be addressed as an array. In Visual Basic, the type reported by sorted.GetType() is System.Linq.Enumerable+WhereSelectEnumerableIterator`2[System.Int32[],System.Int32[]]. In C#, the reported type is System.Linq.OrderedEnumerable`2[System.Int32[],System.Int32].

It appears that in Visual Basic you can access the resulting collection (sorted) as though it's an array. For example, the line Console.WriteLine(sorted(0)(1)) does what you expect: it outputs the second element in the first subarray.

In C#, you cannot address the resulting collection as though it's an array. That is, trying to access sorted[0][1] will generate an error at compile time.

If you want to make sure that you get an array back, just call sorted.ToArray().

If you want to sort the array in place, call Array.Sort, passing it the comparison function.

If you don't want to affect the original array, have LINQ do the sorting. And if you want a copy of the array, as an array, call ToArray on the result that you get back from LINQ.

Sorting a rectangular array

As I pointed out in the original article, sorting a rectangular array has to be done indirectly. Since the entire array is one contiguous block of memory, there is no way to sort the rows. Instead, you have to create a tag array that contains row indices into the original array, and sort that tag array. None of the changes to .NET over the years have changed what you have to do, but language changes have simplified it somewhat.

Let's start by defining the arrays.

[C#]

int[,] a = new int[,] { { 33, 12 }, { 12, 10 }, { 13, 5 }, { 27, 19 } };
int[] tagArray = new int[] { 0, 1, 2, 3 };

[Visual Basic]

Dim a(,) As Integer = {{33, 12}, {12, 10}, {13, 5}, {27, 19}}
Dim tagArray() As Integer = {0, 1, 2, 3}

The advent of Lambda expressions (and, for C#, anonymous methods) removes the need to create an object that implements the IComparer interface. Instead, we can create a Lambda expression and call the Array.Sort method that takes a Comparison delegate:

[C#]

Array.Sort(tagArray, (t1, t2) => { return a[t1, 1].CompareTo(a[t2, 1]); });

[Visual Basic]

Dim sorter As Comparison(Of Integer) = Function(t1 As Integer, t2 As Integer) a(t1, 1).CompareTo(a(t2, 1))
Array.Sort(tagArray, sorter)

Remember, this doesn't actually sort the array, but rather the tag array. To access the array in sorted order, you have to do it indirectly--through the tag array:

[C#]

foreach (var i in tagArray)
{
    for (int j = 0; j < 2; ++j)
    {
        Console.Write("{0}, ", a[i, j]);
    }
    Console.WriteLine();
}

[Visual Basic]

For Each i In tagArray
    For j As Integer = 0 To 1
	Console.Write("{0}, ", a(i, j))
    Next
    Console.WriteLine()
Next

Again, the LINQ code to sort the tag array is very simple:

[C#]

var sorted = from x in tagArray orderby a[x, 1] select x;

[Visual Basic]

Dim sorted = From x In tagArray Order By a(x, 1) Select x

Again, in order to access the array in sorted order, you have to do it indirectly through the tag array.