Sort

In C# we sort collections of elements (like those stored in a List) with built-in methods. We can process arrays and Lists with value elements, and more complex types.

On an array of classes, sorting can be done based on keys (like a specific property of the object). And we can even sort 2 arrays at once—one array is the sort key array.

First example

This program creates a character array of 3 chars. It then calls Array.Sort on the char array reference—and the array elements are reordered.

using System;

char[] array = { 'z', 'a', 'b' };
// Convert array to a string and print it.
Console.WriteLine("UNSORTED: " + new string(array));

// Sort the char array.
Array.Sort<char>(array);
Console.WriteLine("SORTED: " + new string(array));
UNSORTED: zab
SORTED: abz

String arrays

Here we call the static Array.Sort method and use it to sort a string array in-place. The result is an alphabetical sort. With strings, all the characters are considered.

using System;

string[] pets = new string[]
{
    "dog",
    "bird",
    "cat"
};
// Step 1: invoke Array.Sort method on string array.
Array.Sort(pets);

// Step 2: loop over strings in array and print them.
foreach (string pet in pets)
{
    Console.WriteLine(pet);
}
bird
cat
dog

Alphabetize chars

Occasionally, we need to alphabetize the letters in a string. We can convert a string to a character array, and then convert the sorted char array back to a string.

using System;
using System.IO;

string value = "bird";
// Get char array, then sort it, and convert back to string.
var letters = value.ToCharArray();
Array.Sort(letters);
string result = new string(letters);
Console.WriteLine("ALPHABETIZE: {0} -> {1}", value, result);
ALPHABETIZE: bird -> bdir

Query

Next we take a string array and use a LINQ query expression to alphabetically order its contents. We order the strings—not the characters in them.

using System;
using System.Linq;

string[] roadNames = new string[]
{
    "Mill St.",
    "Robin St.",
    "Echo Dr.",
    "Iron Dr."
};

// Sort the roads.
var result = from name in roadNames
             orderby name
             select name;

// Evaluate our query.
foreach (string value in result)
{
    Console.WriteLine(value);
}
Echo Dr.
Iron Dr.
Mill St.
Robin St.

Reverse query

We sort strings from Z to A, not A to Z. This is called reverse alphabetic order. LINQ here is used with a query expression.

using System;
using System.Linq;

string[] trees = new string[]
{
    "Elm",
    "Palm",
    "Redwood",
    "Oak"
};
// Sort the trees from last to first.
var result = from treeName in trees
             orderby treeName descending
             select treeName;

// Write all tree names.
foreach (string value in result)
{
    Console.WriteLine(value);
}
Redwood
Palm
Oak
Elm

List

This is a generic collection, with internal array storage. List not an array type in the C# language. We therefore have to use its separate Sort method.

using System;
using System.Collections.Generic;

List<string> fruitNames = new List<string>()
{
    "mango",
    "pineapple",
    "kiwi",
    "apple",
    "tomato"
};
// Sort the fruit in alphabetical order.
fruitNames.Sort();

// Print the sorted fruit.
foreach (string fruit in fruitNames)
{
    Console.WriteLine(fruit);
}
apple
kiwi
mango
pineapple
tomato

Copy, sort

Many sort methods operate in-place. This means the unsorted, original collection no longer exists. To retain the original order, we must first copy the elements.

using System;
using System.Collections.Generic;

string[] array = { "zebra", "parrot", "ant" };
// Copy the list, then sort it.
List<string> copy = new List<string>(array);
copy.Sort();
// Display the collections.
Console.WriteLine(string.Join(",", array));
Console.WriteLine(string.Join(",", copy));
zebra,parrot,ant
ant,parrot,zebra

Sort 2 things

Suppose we want to sort by one part of your data (an int) and then by another part (another int). This can be done with a comparison method, or with a LINQ expression.

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static List<Tuple<int, int>> GetData()
    {
        var data = new List<Tuple<int, int>>();
        data.Add(new Tuple<int, int>(10, 5));
        data.Add(new Tuple<int, int>(10, 4));
        data.Add(new Tuple<int, int>(1, 6));
        data.Add(new Tuple<int, int>(1, 100));
        return data;
    }

    static int ComparisonTwoTuples(Tuple<int, int> a, Tuple<int, int> b)
    {
        // Here we sort two times at once, first one the first item, then on the second.
        // ... Compare the first items of each element.
        var part1 = a.Item1;
        var part2 = b.Item1;
        var compareResult = part1.CompareTo(part2);
        // If the first items are equal (have a CompareTo result of 0) then compare on the second item.
        if (compareResult == 0)
        {
            return b.Item2.CompareTo(a.Item2);
        }
        // Return the result of the first CompareTo.
        return compareResult;
    }

    static void Main()
    {
        // Use comparison.
        var data = GetData();
        data.Sort(ComparisonTwoTuples);
        Console.WriteLine("::COMPARISON::");
        foreach (var tuple in data)
        {
            Console.WriteLine(tuple);
        }

        // Use LINQ orderby.
        var data2 = GetData();
        var sorted = from tuple in data2
                     orderby tuple.Item1 ascending, tuple.Item2 descending
                     select tuple;
        Console.WriteLine("::ORDERBY::");
        foreach (var tuple in sorted)
        {
            Console.WriteLine(tuple);
        }
    }
}
::COMPARISON::
(1, 100)
(1, 6)
(10, 5)
(10, 4)
::ORDERBY::
(1, 100)
(1, 6)
(10, 5)
(10, 4)

Bool

A bool array is sorted from false to true. When sorting, false is considered as 0 and true is considered as 1. We can use ascending or descending sorts.

using System;

var values = new bool[] { true, false, true };
// Sort bool array.
Array.Sort(values);
foreach (var value in values)
{
    Console.WriteLine(value);
}
False
True
True

Reverse

Reversing an array of elements simply changes the order from back to front. It does not alphabetize or reorder the elements in an ascending or descending order.

using System;

var values = "abc".ToCharArray();
// Reverse the values.
Array.Reverse(values);
foreach (var value in values)
{
    Console.WriteLine(value);
}
c
b
a

Benchmark, quicksort

I tested the sort methods on both arrays and Lists. The performance of these methods was close. Lists and arrays are sorted in about the same amount of time.

using System;
using System.Collections.Generic;
using System.Diagnostics;

const int _max = 100000;
// Create array and list.
var array = new int[1000];
for (int i = 0; i < array.Length; i++)
{
    array[i] = i % 10;
}
var list = new List<int>(array);

// Version 1: sort an array.
var s1 = Stopwatch.StartNew();
for (int i = 0; i < _max; i++)
{
    Array.Sort(array);
    if (array[0] != 0)
    {
        return;
    }
}
s1.Stop();
// Version 2: sort a List.
var s2 = Stopwatch.StartNew();
for (int i = 0; i < _max; i++)
{
    list.Sort();
    if (list[0] != 0)
    {
        return;
    }
}
s2.Stop();
Console.WriteLine(((double)(s1.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns"));
Console.WriteLine(((double)(s2.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns"));
11115.19 ns    Array.Sort
11110.94 ns    List.Sort

Benchmark, LINQ sort

There is a performance penalty to using query expressions and LINQ methods. These methods act on IEnumerable, and this adds indirection.

using System;
using System.Diagnostics;
using System.Linq;

const int _max = 1000000;
// Version 1: create array and sort it with Array.Sort.
var s1 = Stopwatch.StartNew();
for (int i = 0; i < _max; i++)
{
    var data = new int[] { 10, 20, 0, -10, 100, -100 };
    Array.Sort(data);
    if (data[0] != -100)
    {
        return;
    }
}
s1.Stop();
// Version 2: create array, sort it with LINQ, and test first element.
var s2 = Stopwatch.StartNew();
for (int i = 0; i < _max; i++)
{
    var data = new int[] { 10, 20, 0, -10, 100, -100 };
            var result = from element in data
                         orderby element
                         select element;
    if (result.FirstOrDefault() != -100)
    {
        return;
    }
}
s2.Stop();
Console.WriteLine(((double)(s1.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns"));
Console.WriteLine(((double)(s2.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns"));
 52.66 ns    Array.Sort
263.05 ns    Query expression

Benchmark, SortedSet

Collections like SortedSet can keep elements sorted as we add them. These can lead to performance improvements if you need sorted elements.

using System;
using System.Collections.Generic;
using System.Diagnostics;

const int _max = 1000000;
// Version 1: use SortedSet to keep elements sorted.
var s1 = Stopwatch.StartNew();
for (int i = 0; i < _max; i++)
{
    SortedSet<string> set = new SortedSet<string>();
    set.Add("x");
    set.Add("y");
    set.Add("a");
    set.Add("0");
    var first = set.Min;
    var last = set.Max;
    if (first != "0" || last != "y")
    {
        return;
    }
}
s1.Stop();
// Version 2: use List and call Sort to sort elements.
var s2 = Stopwatch.StartNew();
for (int i = 0; i < _max; i++)
{
    List<string> list = new List<string>();
    list.Add("x");
    list.Add("y");
    list.Add("a");
    list.Add("0");
    list.Sort();
    var first = list[0];
    var last = list[list.Count - 1];
    if (first != "0" || last != "y")
    {
        return;
    }
}
s2.Stop();
Console.WriteLine(((double)(s1.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns"));
Console.WriteLine(((double)(s2.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns"));
617.35 ns    SortedSet, 4 Add calls
747.52 ns    List, 4 Add calls, Sort

Summary

Sorting uses method calls. With arrays and lists, it is important to copy a collection first if we want to keep the original. With query syntax we simplify sorting.