LINQ to Objects : How to Sort the Results

LINQ to Objects has comprehensive support for ordering and sorting results. Whether you need to sort in ascending order, descending order using different property values in any sequence, or all the way to writing a specific ordering algorithm of your own, LINQ’s sorting features can accommodate the full range of ordering requirements.

Basic Sorting Syntax

The resulting collection of results from a query can be sorted in any desired fashion, considering culture and case sensitivity. When querying using extension method syntax, the OrderBy, OrderByDescending, ThenBy, and ThenByDescending standard query operators manage this process. The OrderBy and ThenBy operators sort in an ascending order (for example, a to z), and the OrderByDescending and ThenByDescending operators sort in descending order (z to a). Only the first sorting extension can use the OrderBy operators, and each subsequent sorting expression must use the ThenBy operators, of which there can be zero or many depending on how much control you want over the subsorting when multiple elements share equal order after the previous expressions.

The following samples demonstrate sorting a source sequence first by the [w] key, then in descending order by the [x] key, and then in ascending order by the [y] key:

[source].OrderBy([w])
        .ThenByDescending([x])
        .ThenBy([y]);

When using the query expression syntax, each sorting key and the optional direction keyword needs to be separated by a comma character. If the descending or ascending direction keywords are not specified, LINQ assumes ascending order.

from [v] in [source]
orderBy [w], [x] descending, [y]
select [z];

The result from ordering a collection will be an IOrderedEnumerable<T>, which implements IEnumerable<T> to allow further query operations to be cascaded end-to-end.

The ordering extension methods are implemented using a basic but efficient Quicksort algorithm (see http://en.wikipedia.org/wiki/Quicksort for further explanation of how this algorithm works). The implementation LINQ to Objects uses is a sorting type called unstable, which simply means that elements that compare to equal key values may not retain their relative positions to the source collections (although this is simply solved by cascading the result into a ThenBy or ThenByDescending operator). The algorithm is fairly fast, and it lends itself to parallelization, which is certainly leveraged by Microsoft’s investment in Parallel LINQ.

Reversing the Order of a Result Sequence (Reverse)

Another ordering extension method that reverses an entire sequence is the Reverse operator. It is simply called in the form: [source].Reverse();. An important point to note when using the Reverse operator is that it doesn’t test the equality of the elements or carry out any sorting; it simply returns elements starting from the last element, back to the first element. The order returned will be the exact reciprocal of the order that would have been returned from the result sequence. The following example demonstrates the Reverse operator, returning T A C in the Console window:

string[] letters = new string[] { "C", "A", "T" };
var q = letters.Reverse();
foreach (string s in q)
    Console.Write(" " + s);

Case Insensitive and Cultural-specific String Ordering

Any standard query operator that involves sorting has an overload that allows a specific comparer function to be supplied (when written using extension method syntax). The .NET class libraries contain a handy helper class called StringComparer, which has a set of predefined static comparers ready for use. The comparers allow us to alter string sorting behavior, controlling case-sensitivity and current culture (the language setting for the current thread). Table 1 lists the static Comparer instances that can be used in any OrderBy or ThenBy ascending or descending query operator.

Table 1. The Built-in StringComparer Functions to Control String Case Sensitivity and Culture-aware String Ordering

Comparer	Description
CurrentCulture	Performs a case-sensitive string comparison using the word comparison rules of the current culture.
CurrentCultureIgnoreCase	Performs case-insensitive string comparisons using the word comparison rules of the current culture.
InvariantCulture	Performs a case-sensitive string comparison using the word comparison rules of the invariant culture.
InvariantCultureIgnoreCase	Performs a case-insensitive string comparison using the word comparison rules of the invariant culture.
Ordinal	Performs a case-sensitive ordinal string comparison.
OrdinalIgnoreCase	Performs a case-insensitive ordinal string comparison.

Listing 1 demonstrates the syntax and effect of using the built-in string comparer instances offered by the .NET Framework. The Console output is shown in Output 1, where the default case-sensitive result can be forced to case-insensitive.

Listing 1. Case and culture sensitive/insensitive ordering using StringComparer functions—see Output 1

string[] words = new string[] { "jAnet", "JAnet", "janet", "Janet" }; var cs = words.OrderBy(w => w); var ci = words.OrderBy(w => w, StringComparer.CurrentCultureIgnoreCase); Console.WriteLine("Original:"); foreach (string s in words) Console.WriteLine(" " + s); Console.WriteLine("Case Sensitive (default):"); foreach (string s in cs) Console.WriteLine(" " + s); Console.WriteLine("Case Insensitive:"); foreach (string s in ci) Console.WriteLine(" " + s);

Output 1.

Original: jAnet JAnet janet Janet Case Sensitive (default): janet jAnet Janet JAnet Case Insensitive: jAnet JAnet janet Janet

Specifying Your Own Custom Sort Comparison Function

To support any sorting order that might be required, custom sort comparison classes are easy to specify. A custom compare class is a class based on a standard .NET Interface called IComparer<T>, which exposes a single method: Compare. This interface is not specifically for LINQ; it is the basis for all .NET Framework classes that require sorting (or custom sorting) capabilities.

Comparer functions work by returning an integer result, indicating the relationship between a pair of instance types. If the two types are deemed equal, the function returns zero. If the first instance is less than the second instance, a negative value is returned, or if the first instance is larger than the second instance, the function returns a positive value. How you equate the integer result value is entirely up to you.

To demonstrate a custom IComparer<T>, Listing 2 demonstrates a comparison function that simply shuffles (in a random fashion) the input source. The algorithm simply makes a random choice as to whether two elements are less than or greater than each other. Output 3-8 shows the Console output from a simple sort of a source of strings in an array, although this result will be different (potentially) each time this code is executed.

Listing 2. Ordering using our custom IComparer<T> implementation to shuffle the results—see Output 2

public class RandomShuffleStringSort<T> : IComparer<T> { internal Random random = new Random(); public int Compare(T x, T y) { // get a random number: 0 or 1 int i = random.Next(2); if (i == 0) return -1; else return 1; } } string[] strings = new string[] { "1-one", "2-two", "3-three", "4-four", "5-five" }; var normal = strings.OrderBy(s => s); var custom = strings.OrderBy(s => s, new RandomShuffleStringSort<string>()); Console.WriteLine("Normal Sort Order:"); foreach (string s in normal) { Console.WriteLine(" " + s); } Console.WriteLine("Custom Sort Order:"); foreach (string s1 in custom) { Console.WriteLine(" " + s1); }

Output 2.

Normal Sort Order: 1-one 2-two 3-three 4-four 5-five Custom Sort Order: 1-one 2-two 5-five 4-four 3-three

A common scenario that has always caused me trouble is where straight alphabetical sorting doesn’t properly represent alpha-numeric strings. The most common example is alphabetic sorting strings such as File1, File10, File2. Naturally, the desired sorting order would be File1, File2, File10, but that’s not alphabetical. A custom IComparer that will sort the alphabetic part and then the numeric part separately is needed to achieve this common scenario. This is called natural sorting.

Listing 3 and Output 3 demonstrate a custom sort class that correctly orders alpha strings that end with numbers. Anywhere this sort order is required, the class name can be passed into any of the OrderBy or ThenBy extension methods in the following way:

string[] partNumbers = new string[] { "SCW10", "SCW1",
    "SCW2", "SCW11", "NUT10", "NUT1", "NUT2", "NUT11" };

var custom = partNumbers.OrderBy(s => s,
    new AlphaNumberSort());

The code in Listing 3 first checks if either input string is null or empty. If either string is empty, it calls and returns the result from the default comparer (no specific alpha-numeric string to check). Having determined that there are two actual strings to compare, the numeric trailing section of each string is extracted into the variables numericX and numericY. If either string doesn’t have a trailing numeric section, the result of the default comparer is returned (if no trailing numeric section exists for one of the strings, then a straight string compare is adequate). If both strings have a trailing numeric section, the alpha part of the strings is compared. If the strings are different, the result of the default comparer is returned (if the strings are different, the numeric part of the string is irrelevant). If both alpha parts are the same, the numeric values in numericX and numericY are compared, and that result is returned. The final result is that all strings are sorted alphabetically, and where the string part is the same between elements, the numeric section controls the final order.

Listing 3. Sorting using a custom comparer. This comparer properly sorts strings that end with a number—see Output 3

Code View: Scroll / Show All public class AlphaNumberSort : IComparer<string> { public int Compare(string a, string b) { StringComparer sc = StringComparer.CurrentCultureIgnoreCase; // if either input is null or empty, // do a straight string comparison if (string.IsNullOrEmpty(a) || string.IsNullOrEmpty(b)) return sc.Compare(a, b); // find the last numeric sections string numericX = FindTrailingNumber(a); string numericY = FindTrailingNumber(b); // if there is a numeric end to both strings, // we need to investigate further if (numericX != string.Empty && numericY != string.Empty) { // first, compare the string prefix only int stringPartCompareResult = sc.Compare( a.Remove(a.Length - numericX.Length), b.Remove(b.Length - numericY.Length)); // the strings prefix are different, // return the comparison result for the strings if (stringPartCompareResult != 0) return stringPartCompareResult; // the strings prefix is the same, // need to test the numeric sections as well double nX = double.Parse(numericX); double nY = double.Parse(numericY); return nX.CompareTo(nY); } else return sc.Compare(a, b); } private static string FindTrailingNumber(string s) { string numeric = string.Empty; for (int i = s.Length - 1; i > -1; i--) { if (char.IsNumber(s[i])) numeric = s[i] + numeric; else break; } return numeric; } } string[] partNumbers = new string[] { "SCW10", "SCW1", "SCW2", "SCW11", "NUT10", "NUT1", "NUT2", "NUT11" }; var normal = partNumbers.OrderBy(s => s); var custom = partNumbers.OrderBy(s => s, new AlphaNumberSort()); Console.WriteLine("Normal Sort Order:"); foreach (string s in normal) Console.WriteLine(" " + s); Console.WriteLine("Custom Sort Order:"); foreach (string s in custom) Console.WriteLine(" " + s);

Output 3.

Normal Sort Order: NUT1 NUT10 NUT11 NUT2 SCW1 SCW10 SCW11 SCW2 Custom Sort Order: NUT1 NUT2 NUT10 NUT11 SCW1 SCW2 SCW10 SCW11

Note

To achieve the same result in most Windows operating systems (not Windows 2000, but ME, XP, 2003, Vista, and Windows 7) and without guarantee that it won’t change over time (it bears the following warning “Note Behavior of this function, and therefore the results it returns, can change from release to release. It should not be used for canonical sorting applications”), Microsoft has an API that it uses to sort files in Explorer (and presumably other places).

internal static class Shlwapi
{
    // http://msdn.microsoft.com/
    // en-us/library/bb759947(VS.85).aspx
    [DllImport("shlwapi.dll",
                CharSet = CharSet.Unicode)]
    public static extern int StrCmpLogicalW(
        string a,
        string b);
}

public sealed class
    NaturalStringComparer: IComparer<string>
{
    public int Compare(string a, string b)
    {
        return Shlwapi.StrCmpLogicalW(a, b);
    }
}