C# sorting, stability, and Array.BinarySearch
Sort arrays and records, keep equal items in order with LINQ, and find insertion points.
using System;
using System.Linq;
class Program {
static void Main() {
int[] numbers = { 5, 2, 9, 1, 5, 6 };
Array.Sort(numbers);
Console.WriteLine(string.Join(" ", numbers));
int found = Array.BinarySearch(numbers, 9);
int missing = Array.BinarySearch(numbers, 4);
Console.WriteLine("index of 9: " + found);
Console.WriteLine("4 would be inserted at " + ~missing);
var people = new[] { (Name: "Ada", Age: 30), (Name: "Bo", Age: 25), (Name: "Cy", Age: 30), (Name: "Di", Age: 25) };
var byAge = people.OrderBy(p => p.Age);
Console.WriteLine(string.Join(",", byAge.Select(p => p.Name)));
string[] words = { "pear", "Apple", "fig" };
Array.Sort(words, StringComparer.OrdinalIgnoreCase);
Console.WriteLine(string.Join(",", words));
}
}1 2 5 5 6 9 index of 9: 5 4 would be inserted at 2 Bo,Di,Ada,Cy Apple,fig,pear
Explanation
Array.Sort sorts an array in place, with an optional comparison. List<T>.Sort and Array.Sort use an introspective sort that is not stable, so equal elements may change order. LINQ's OrderBy and ThenBy are stable and return a new sequence, which makes them the right choice for sorting records by several keys.
Array.BinarySearch works on a sorted array. It returns the index when the value is found. If it is not found, it returns the bitwise complement of the index where the value would be inserted, which is always negative. Applying ~ to the result gives the insertion point, so the array can stay sorted when a value is inserted there.
Explore the dry run
using System;using System.Linq; class Program { static void Main() { int[] numbers = { 5, 2, 9, 1, 5, 6 }; Array.Sort(numbers); Console.WriteLine(string.Join(" ", numbers)); int found = Array.BinarySearch(numbers, 9); int missing = Array.BinarySearch(numbers, 4); Console.WriteLine("index of 9: " + found); Console.WriteLine("4 would be inserted at " + ~missing); var people = new[] { (Name: "Ada", Age: 30), (Name: "Bo", Age: 25), (Name: "Cy", Age: 30), (Name: "Di", Age: 25) }; var byAge = people.OrderBy(p => p.Age); Console.WriteLine(string.Join(",", byAge.Select(p => p.Name))); string[] words = { "pear", "Apple", "fig" }; Array.Sort(words, StringComparer.OrdinalIgnoreCase); Console.WriteLine(string.Join(",", words)); }}Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Sort in place into ascending order. | — | — | |
| Sorted numbers. | — | 1 2 5 5 6 9 | |
| 4 is not present. The result is the complement of the insertion index, a negative number. | — | 1 2 5 5 6 9 | |
| 9 is found at index 5. | — | 1 2 5 5 6 9 index of 9: 5 | |
| ~ recovers the insertion index: 4 belongs between 2 and 5, at index 2. | — | 1 2 5 5 6 9 index of 9: 5 4 would be inserted at 2 | |
| OrderBy is stable, so people of the same age keep their original order. | — | 1 2 5 5 6 9 index of 9: 5 4 would be inserted at 2 | |
| Bo and Di (25) come before Ada and Cy (30), each pair in its original order. | — | 1 2 5 5 6 9 index of 9: 5 4 would be inserted at 2 Bo,Di,Ada,Cy | |
| A case-insensitive comparer sorts Apple before fig and pear. | — | 1 2 5 5 6 9 index of 9: 5 4 would be inserted at 2 Bo,Di,Ada,Cy Apple,fig,pear |
Cost and common mistakes
Sorting O(n log n); BinarySearch O(log n).
- Calling BinarySearch on an array that is not sorted gives meaningless results without any error.
- List<T>.Sort and Array.Sort are not stable. Use OrderBy when the order of equal items matters.
- The default string comparison is culture-sensitive. Pass StringComparer.Ordinal for code-like text.
Try it yourself
How would you insert 4 so that the array stays sorted?
Reveal answer and reasoning
Compute the insertion index ~missing (2) and insert there, for example with List<int>.Insert(index, 4).