C# sorting, stability, and Array.BinarySearch

Before you start

C# arrays and LINQ.

Sort arrays and records, keep equal items in order with LINQ, and find insertion points.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

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));
  }
}

Output

1 2 5 5 6 9
index of 9: 5
4 would be inserted at 2
Bo,Di,Ada,Cy
Apple,fig,pear

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1using System;

2using System.Linq;

4class Program {

5 static void Main() {

6 int[] numbers = { 5, 2, 9, 1, 5, 6 };

7 Array.Sort(numbers);

8 Console.WriteLine(string.Join(" ", numbers));

10 int found = Array.BinarySearch(numbers, 9);

11 int missing = Array.BinarySearch(numbers, 4);

12 Console.WriteLine("index of 9: " + found);

13 Console.WriteLine("4 would be inserted at " + ~missing);

15 var people = new[] { (Name: "Ada", Age: 30), (Name: "Bo", Age: 25), (Name: "Cy", Age: 30), (Name: "Di", Age: 25) };

16 var byAge = people.OrderBy(p => p.Age);

17 Console.WriteLine(string.Join(",", byAge.Select(p => p.Name)));

19 string[] words = { "pear", "Apple", "fig" };

20 Array.Sort(words, StringComparer.OrdinalIgnoreCase);

21 Console.WriteLine(string.Join(",", words));

22 }

23}

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

Prepared trace of the published program. Some rows group repeated iterations.
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

Behind the scenes

How C# processes this code

C# compiles to code for the .NET runtime, which invokes the program entry point.

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