C# Sort ExamplesReorder array elements with Array.Sort and List elements with Sort. Review sort performance.
Sort. For collections of 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.
Sort methods. We can sort an object array 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.
An example. To begin, this program creates a character array of 3 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.
Also We use the string constructor on our char array to print the strings to the console.
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)); } }
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.
Step 1 We pass the string array reference to the Array.Sort static method. No value is returned by Array.Sort.
Step 2 We use the foreach-loop to print out all the pet names. Strings can be sorted in the same way as chars—with Array.Sort.
C# program that uses Array.Sort
using System; class Program { static void Main() { 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
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); } } }
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.
Orderby The order by keyword is not a method. Instead it compiles into a method call. It is a query clause.
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); } } }
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); } } }
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.
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)); } }
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); } } }
::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.
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")); } }
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.
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")); } }
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.
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")); } }
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
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.
CompareTo This is used as part of IComparable. CompareTo returns 0, 1, or -1 to indicate ordering of 2 elements.
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.
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 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.
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 Files, Sizes
Sort KeyValuePair List
Sort Strings, Length
Algorithms, preprocess. It is possible to modify each value before applying a sorting method. For example, leading chars can be changed.
Sort Ignore Lead 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
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.
© 2007-2021 sam allen. see site info on the changelog