email article printer friendly get the code more resources

Sort in .NET
Learn how to implement and customize sorting for collections containing various data types.
by Doug Thews

September 20, 2004

Technology Toolbox: VB.NET, Visual Studio .NET 2003

Sorting is one of the most commonly used algorithms in any application. Whether you're sorting data in arrays, data tables, or controls, sorting provides users with a logical view of information that's easy for them to digest.

Both ADO.NET and the majority of list controls support sorting natively by default, and a plethora of articles and quickstart examples show you just how this works. I'll show you how to implement and customize sorting for lists containing various data types.

Several specific collections in the .NET Framework implement the Sort() method, including Array and ArrayList. You get native support for the Sort() method if you define your collection class as ArrayList or inherit from the ArrayList class:

myArrayList.Sort()

You need to implement your own comparator and sorting logic if you base your collection off classes such as CollectionBase, Hashtable, DictionaryBase, or Queue. Many developers inherit their collection classes from either the Array or ArrayList classes if they need sort functionality.

The Sort() method uses a standard quicksort algorithm to sort data in collections. The quicksort algorithm works by a method frequently called "divide and conquer." It selects an element from the list randomly and breaks the list into two pieces—those whose elements are smaller than a given number, and those whose elements are larger than that number. It then applies this logic to each piece recursively until the list is completely sorted.

For example, take this list of numbers—5, 8, 2, 9, 1, 4, 7, 3—and use quicksort to sort them (see Table 1). First, select a number from the list at random (let's say 4), then partition the list into two pieces. The left side contains elements less than 4, and the right side contains elements greater than 4 (these are placed in their same order—you don't do any subsorting here).

Now, perform the same action recursively on the left and then the right side until you end up with no more elements to partition on any side. Table 1 describes the detail of how to quicksort the entire list of numbers to get the end product of (1, 2, 3, 4, 5, 7, 8).