C# Sort

Array Class Collections File Keyword String .NET ASP.NET Cast Compression Data Delegate Directive Enum Exception If Interface LINQ Loop Method Number Process Property Regex Sort StringBuilder Struct Switch Time Windows WPF

Sort

There is a natural order of things. Day alternates with night. And human beings create new patterns. Numbers and letters come one after another. All these things can be sorted. We use powerful built-in methods.

Example

Please consider this simple example. The program uses a character array of three chars: they are not sorted. It calls Array.Sort on the char array reference. And the array elements (stored on the heap) 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.1

Program that sorts character array: C#

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

Intro

String array

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. We test all these methods as we continue.

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: little new is introduced from the previous sample.

Array.SortArray type

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

Program that uses Array.Sort: C#

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

System.Linq namespace

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

Tip:You can see that the orderby keyword results in the same output as the Array.Sort method.

About part

When you use the query expression in LINQ, it returns an IEnumerable collection. This just means it is a collection that you have to enumerate (loop over) to get with the foreach-loop.

IEnumerableForeach
Program that uses LINQ: C#

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

Descending: sort order

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. It returns an enumeration of the original strings ordered from Z to A.

This example is the same as in the previous one, except it uses different strings and the descending keyword. Ascending means to go from lowest to highest (A to Z), while descending means to go from highest to lowest (Z to A).

Note:The orderby keyword is not a method per se.
It compiles into a method call.
It is a query expression.

orderbyascendingdescending
Program that uses LINQ descending: C#

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

Framework: NET

The List and ArrayList collections both have sorting methods. We describe and provide examples for their use.
If you want to sort your List
or ArrayList,
these are the best options.

Sort ListArrayList Sort

The Dictionary collection has both keys and values, but no way to sort these that is built into the .NET Framework. You can instead acquire the Keys or Values collections and sort them.

Sort Dictionary

List

List

List<string> indicates a generic List collection of strings. Internally it is stored as an array. But it is not an array type in the C# language. We therefore have to use its separate Sort method.

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

List
Program that uses List: C#

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

Copy: new object copied

Many sort methods sort in-place. This means the unsorted, original collection no longer exists. If you want to retain the original order in a parallel collection, you must first copy the elements to a new collection.

The List elements are sorted, but the original array is left alone. Please note that this program requires the .NET Framework version 4.0 or later to compile. It uses newer overloads of string.Join.

string.Join
Program that sorts copy: C#

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

Performance optimization

Originally, this page showed a benchmark of the sorting methods on collections of varying sizes. The performance of these methods was very close. And the benchmarks were not helpful or interesting so I removed them.

Note:Because these methods are all implemented with quicksort internally, the overall speed is going to be close.

IComparable

Convert

You can implement sorting directly on a class. Then when you try to sort a collection of that type, your custom sorting method will be used automatically. For more information, read about the IComparable<T> 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

What happens internally? We see that the List sort method is implemented with Array.Sort. This is why it performs similarly to Array.Sort. To examine the internals of the List sorting method, please open it in IL Disassembler.

IL Disassembler TutorialAbout part

Type specifier:The Array.Sort method shown is a generic method, which means you must specify the type when you call the method.

Note:The C# compiler can derive the type implicitly in many cases. You 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

Reverse

To reverse 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. We reverse an array of words or the characters in a string.

Reverse WordsReverse String

Algorithms

Objects: dots

Do you need a sorting algorithm that treats the string "300" as greater than "31"? The alphanumeric sorting algorithm will actually parse substrings into numbers. Another algorithm detects whether an array is pre-sorted.

Alphanumeric SortNumber String SortIs Sorted

Property sorting:Sometimes you may want to sort an array based on some characteristic of each element.

File Size SortKeyValuePair SortString Length SortTuple SortAbout part

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

Mousetraps

Concept: a discussion topic

In computer science, a common goal is the creation of a faster sorting algorithm. This sounds easier than it is. Some algorithms work better on certain data sets than quicksort. 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. Sedgewick, p. 317

Summary

C# programming language

Sorting is most easily done with method calls. With arrays and lists, it is important to copy your collection first if you want to keep the original version. And the System.Linq namespace helps simplify sorts.

Review:The .NET Framework uses quicksort.
Lists and arrays (through Array.Sort) use this algorithm.
They share implementations.

C#