C# Sort Examples: Arrays and Lists

Reorder array elements with Array.Sort and List elements with Sort. Review sort performance.

Sort. An elephant roams the savannah. A bird is seen in the sky. On this bird a mite lives. Animals come in all sizes—we sort them from large to small.

Sort methods. For words and numbers, an order can be imposed. To sort these in C#, we use built-in methods. We consider arrays, Lists, and even Dictionaries.

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

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

Also: We use the string constructor on our char array to print the strings to the console.

String Constructor

C# program that sorts character array using System; class Program { static void Main() { 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)); } } Output 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. This console program demonstrates Array.Sort.Sort: Array

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[] colors = new string[] { "orange", "blue", "yellow", "aqua", "red" }; // Call Array.Sort method. Array.Sort(colors); foreach (string color in colors) { Console.WriteLine(color); } } } Output aqua blue orange red yellow

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 foreach.

C# program that uses LINQ using System; using System.Linq; class Program { static void Main() { 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); } } } Output 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.

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

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[] 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); } } } Output 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.

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

Important: The fruit names are sorted alphabetically, not by how tasty the fruit is. This is why "apple" comes first.

C# program that uses List using System; using System.Collections.Generic; class Program { static void Main() { 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); } } } Output 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.

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

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.

ComparisonTwoTuples: Calls CompareTo twice: it first compares the first item. If that is equal, it uses CompareTo on the second int.

Query: We use an orderby clause with a second part. Notice how we can specify ascending and descending.

Note: The CompareTo method (used in ComparisonTwoTuples) returns 0 when two values compare to be equal.

Result: We sort on the first item in the tuples—from low to high. And we sort on the second item, from high to low (descending).

C# program that sorts 2 things at once 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); } } } Output ::COMPARISON:: (1, 100) (1, 6) (10, 5) (10, 4) ::ORDERBY:: (1, 100) (1, 6) (10, 5) (10, 4)

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.

Info: In these modern times, optimized algorithms are built into frameworks. The methods on this page are implemented with quicksort.

Version 1: We sort an array of 1000 elements that are not in ascending order, but are not random. Modulo returns alternating elements.

Modulo

Version 2: We sort a List with the same elements as the array. Only the first sort moves the elements around.

Result: The array and List are processed in about the same time, so the underlying algorithm is likely the same in each case.

C# program that benchmarks array, List sorting using System; using System.Collections.Generic; using System.Diagnostics; class Program { const int _max = 100000; static void Main() { // 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")); } } Output 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.IEnumerable

Version 1: This version of the code uses Array.Sort on a small array of ints to sort in ascending order.

Version 2: Here we use a query expression, and the FirstOrDefault() method, to perform the same tasks as version 1.

Result: There is significant overhead to using LINQ on small int arrays. For low-level things like int arrays, prefer Array.Sort.

C# program that benchmarks Array.Sort, LINQ using System; using System.Diagnostics; using System.Linq; class Program { const int _max = 1000000; static void Main() { // 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")); } } Output 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.SortedSet

Version 1: We create a SortedSet and add 4 strings to it. Then we access Min and Max to ensure the elements are sorted.

Version 2: We create a List and add 4 strings to it, and then call Sort() to order the elements.

Result: Keeping the elements sorted as we add them is faster overall. Note that the SortedSet cannot accept duplicate elements.

C# program that benchmarks SortedSet, List Sort using System; using System.Collections.Generic; using System.Diagnostics; class Program { const int _max = 1000000; static void Main() { // 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")); } } Output 617.35 ns SortedSet, 4 Add calls 747.52 ns List, 4 Add calls, Sort

List, ArrayList. 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: List Sort: ArrayList

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

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.bool Sort

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

CompareTo: This is used as part of IComparable. CompareTo returns 0, 1, or -1 to indicate ordering of 2 elements.

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 Class, Method

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: Array Reverse: IEnumerable Reverse: String Reverse: Words

Algorithms, alphanumeric. An alphanumeric sorting algorithm will treat the string "300" as greater than "31." This helps sort strings with numbers in them.Alphanumeric Sort

Algorithms, IsSorted. Is a list sorted? It is possible to sort a copy and see if the copy is equal to the original. But a simple iterative loop is faster and clearer.IsSorted

Algorithms, sort on properties. Sometimes we may want to sort an array based on some characteristic of each element, like a key value or property.Sort: File Sizes Sort: KeyValuePairs Sort: String Lengths Sort: Tuples

Algorithms, preprocess. It is possible to modify each value before applying a sorting method. For example, leading chars can be changed.Sort: Ignore Leading Chars Sort: Number Strings

Algorithms, characters. Occasionally, we need to alphabetize the letters in a string. This helps with computing anagrams for words.Alphabetize String

Research. 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.

Quote: 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++ Third Edition).

A 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.

The Dev Codes

.Net

.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

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

C# Sort Examples: Arrays and Lists

Related Links:

.Net

Java

Related Links