Sorting in C#

In order to sort a static array we can use the Array.Sort() method which sorts the elements of a given array in ascending order (default), descending order or user-defined order.

Similarly, if we want to sort a List<T>, we can call its Sort() method which works the same way.

Important: in C#, sorting in reverse or with a specified order using a comparison function works directly on arrays of numbers such as int[], because C# generics work with int itself and there is no separate boxed type to convert to.

Syntax:

Let's see some examples below. Sorting an array of integers in ascending order

int[] numbers = {11, 3, 7, 5, 2};

Array.Sort(numbers); // numbers becomes [2, 3, 5, 7, 11]

Sorting a List of integers in descending order

List<int> arr = new List<int> {11, 3, 7, 5, 2};

arr.Sort((a, b) => b - a); // arr becomes [11, 7, 5, 3, 2]

Sorting an array of integers in descending order

int[] numbers = {11, 3, 7, 5, 2};

Array.Sort(numbers, (a, b) => b - a); // numbers becomes [11, 7, 5, 3, 2]

Sorting an array of Strings in descending order

string[] names = {"Mircea", "Andy", "Xavier", "Michael", "Christina"};

Array.Sort(names, (a, b) => string.CompareOrdinal(b, a)); // --> {"Xavier", "Mircea", "Michael", "Christina", "Andy"}

Sort with custom function (comparator):

Array.Sort() method supports a basic comparison function that we can use to specify how we want to sort:

int Compare(int a, int b) {
    return a - b;
}

This can be written as a lambda function (nameless function we can easily pass to Array.Sort()) as follows:

(a, b) => {
    return a - b;
}

If the function just returns one thing, we can write it as follows:

(a, b) => a - b

When Array.Sort() compares two values, it sends the values to the compare function, and sorts the values according to the returned (negative, zero, positive) value:

• If the result is negative a is sorted before b.
• If the result is positive b is sorted before a.
• If the result is 0 no changes are done with the sort order of the two values.

All we need to is using the compare function (as a lambda function) inside the Array.Sort() method:

int[] numbers = {3, 23, 12};

// using the short version of the lambda function
Array.Sort(numbers, (a, b) => a - b); // --> 3, 12, 23

To demonstrate a basic example, let’s assume the requirement for ordering a specific list is the length of the strings in the list, shortest to longest. We will be using the Length property of each string to compare them.

string[] words = {"banana", "pie", "Washington", "book"};

Array.Sort(words, (a, b) => a.Length - b.Length); // --> {"pie", "book", "banana", "Washington"}

Example: sorting array of pairs

Let's say we want to sort an array, where each element is another array consisting of two numbers.

This time we will be using int[][] (an array of arrays): each element is an int[], and we tell Array.Sort() how to compare two of them

int[][] pairs = { new int[] {1, 5}, new int[] {12, 5}, new int[] {10, 1}, new int[] {1, 3} };

Array.Sort(pairs, (a, b) => {
    // in case the first values of each pair are equal,
    // compare them using their second values
    if (a[0] == b[0]) {
        return a[1] - b[1];
    }
    return a[0] - b[0];
});
// pairs --> [[1, 3], [1, 5], [10, 1], [12, 5]]

Time Complexity:

Sorting an array via Array.Sort() takes O(n * log n * C) time, where C is the time taken to compare two elements from the array.

It takes O(1) (constant time) to compare two numbers, therefore sorting an array of numbers takes O(n log n).

However, it takes O(L) to compare two strings, therefore sorting an array of strings takes O(n * log n * L), where L is the average length of the strings.

Space Complexity:

The Array.Sort() method sorts the elements of an array in place (transforms the array directly, without creating a second array), so it needs no extra array; its internal recursion uses only O(log n) extra space.

Assignment
Follow the Coding Tutorial and let's sort some arrays.

Hint
Look at the examples above if you get stuck.