C#

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Sorting. In our universe, we recognize a natural order of things. Day alternates with night. Stars take predictable positions in the sky. Order is everywhere.


Human beings create new patterns, often with letters, with numbers. To sort these, we use built-in methods. And we develop comparers to sort based on different properties.


A simple example. This program uses a character array of three chars. It calls Array.Sort on the char array reference. And the array elements are reordered.

Tip: There is no need to assign to the result of Array.Sort. This would result in a compile-time error: it returns void.

Finally: We use a foreach-loop upon the array elements. We print them to the console. They are in alphabetical order.

Based on: .NET 4.5

C# program that sorts character array

using System;

class Program
{
    static void Main()
    {
	char[] array = { 'z', 'a', 'b' }; // Input array.
	Array.Sort<char>(array);          // Call sort.
	foreach (var c in array)
	    Console.WriteLine(c);
    }
}

Output

a
b
z

Methods. There are many collection sorting methods. To make choosing even harder, there is also LINQ query syntax. LINQ introduces another entire syntax to the C# language.

Also: String arrays are used frequently in sorting operations. Please find more information about this common type.

String Array

Strings. Here we call the static Array.Sort method and use it to sort a string array in-place. The result is an alphabetical sort. This console program demonstrates Array.Sort.

Array.Sort

Tip: This example is similar to the one with char arrays. In fact, they are the same except for the element data type.

C# program that uses Array.Sort

using System;

class Program
{
    static void Main()
    {
	string[] a = new string[]
	{
	    "Egyptian",
	    "Indian",
	    "American",
	    "Chinese",
	    "Filipino",
	};
	Array.Sort(a);
	foreach (string s in a)
	{
	    Console.WriteLine(s);
	}
    }
}

Output

American
Chinese
Egyptian
Filipino
Indian

Query. Next we take a string array and use a LINQ query expression to alphabetically order its contents. Please note that we order the strings, not the letters (characters) in them.

Note: We see that the orderby keyword results in the same output as the Array.Sort method.

However: When we use a query, it returns an IEnumerable collection. This is a collection that we enumerate (loop over) with for each.

IEnumerableForeach
C# program that uses LINQ

using System;
using System.Linq;

class Program
{
    static void Main()
    {
	string[] a = new string[]
	{
	    "Indonesian",
	    "Korean",
	    "Japanese",
	    "English",
	    "German"
	};
	var sort = from s in a
		   orderby s
		   select s;

	foreach (string c in sort)
	{
	    Console.WriteLine(c);
	}
    }
}

Output

English
German
Indonesian
Japanese
Korean

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.

Ascending: Means to go from lowest to highest (A to Z). This is the default ordering, so we do not need to specify it.

ascending

Descending: A descending order means to go from highest to lowest (Z to A). We must explicitly specify this.

descending

Orderby: The order by keyword is not a method. Instead it compiles into a method call. It is a query clause.

orderby
C# program that uses LINQ descending

using System;
using System.Linq;

class Program
{
    static void Main()
    {
	string[] a = new string[]
	{
	    "French",
	    "Italian",
	    "European",
	    "Irish",
	    "Vietnamese"
	};
	var desc = from s in a
		   orderby s descending
		   select s;

	foreach (string c in desc)
	{
	    Console.WriteLine(c);
	}
    }
}

Output

Vietnamese
Italian
Irish
French
European

Collections. List and ArrayList both have sorting methods. If you want to sort a List or ArrayList, these are the best options. No conversions are needed.

Sort ListArrayList Sort

Dictionary. This collection has both keys and values, but no way to directly sort them. We can instead acquire the Keys or Values collections and sort them.

Sort Dictionary

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.

Also: We can use LINQ with the same syntax on List as used on arrays. Both arrays and Lists implement the IEnumerable interface.

List
C# program that uses List

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	List<string> l = new List<string>()
	{
	    "Australian",
	    "Mongolian",
	    "Russian",
	    "Austrian",
	    "Brazilian"
	};
	l.Sort();
	foreach (string s in l)
	{
	    Console.WriteLine(s);
	}
    }
}

Output

Australian
Austrian
Brazilian
Mongolian
Russian

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.

Here: The List elements are sorted, but the original array is left alone. This requires the .NET Framework version 4.0 or later to compile.

Join
C# program that sorts copy

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	string[] array = { "zebra", "parrot", "ant" };

	List<string> copy = new List<string>(array);
	copy.Sort();

	Console.WriteLine(string.Join(",", array));
	Console.WriteLine(string.Join(",", copy));
    }
}

Output

zebra,parrot,ant
ant,parrot,zebra

Speed. I tested the sorted methods on collections of varying sizes. The performance of these methods was close. And the benchmarks were not helpful or interesting, so I removed them.

Note: Because these methods are all implemented internally with quicksort, the overall speed will remain close.


IComparable. We can implement sorting on a class. Then when we sort a collection of that type, the custom sorting method is automatically used. Please read about the IComparable interface.

IComparable

CompareTo: We test the CompareTo method in the .NET Framework. Once you understand how this works, making your own becomes easier.

CompareTo

Internals. The List sort method is implemented with Array.Sort. This is why it performs similarly to Array.Sort. To examine the internals of the method, please open it in IL Disassembler.

IL Disassembler

Type specifier: The Array.Sort method shown is a generic method. We specify the type when we call the method.

Note: The C# compiler can derive the type implicitly in many cases. We do not need to always specify it.

Generic Method
Part of implementation of List.Sort: C#

Array.Sort<T>(this._items, index, count, comparer);

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.

Reverse WordsReverse String

Algorithms. An alphanumeric sorting algorithm will treat the string "300" as greater than "31." Another algorithm detects whether an array is presorted.

Alphanumeric SortNumber String SortIs Sorted

Property sorting: Sometimes we may want to sort an array based on some characteristic of each element, like a key value or property.

File Size SortKeyValuePair SortString Length SortTuple: Sort

Modify values: It is possible to modify each value before applying a sorting method. For example, leading chars can be changed.

Sort Ignore Leading Chars

Characters: Occasionally, we need to alphabetize the letters in a string. This helps with computing anagrams for words.

Alphabetize String

In computer science, a common goal is a faster sorting algorithm. This is hard. Some work better than quicksort on certain data sets. But a universally faster algorithm is elusive.

Thus: I recommend sticking with the .NET Framework's sorting algorithms. An alternative is to keep your data sorted as you add it.

It is tempting to try to develop ways to improve quicksort. A faster sorting algorithm is computer science's "better mousetrap," and quicksort is a venerable method that seems to invite tinkering.

Algorithms in C++

Sorting is easily done with 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.


The .NET Framework uses quicksort. Lists and arrays (through Array.Sort) use this algorithm. They share implementations. These methods are fast, ready and tested.