Title: Compare sorting algorithms in C#, part 1 of 5 (Array.Sort)

This post begins a series of articles about sorting algorithms. Much of the text originally appeared in the December 1995 issue of Visual Basic Developer magazine, a publication that seems to no longer exist. All of these posts include the same download: an example program that demonstrates all of the sorting algorithms described in the articles. You can use the example to compare the different algorithms under difference circumstances. Keep in mind that some of the algorithms may take a very long time depending on the kind of data you are sorting. For example, Bubblesort will take a very long time to sort 1 million randomly arranged items.

Why So Many Algorithms?

The .NET Framework's Array class provides a Sort method that sorts an array very quickly, apparently by using Quicksort. In most cases, you can simply use Array.Sort to get very good performance. Other built-in sorting tools such as LINQ use the same method so they also provide good performance.

The Framework's implementation is quite good, so you are unlikely to beat it's performance for "random" data, so why should you bother to learn how these algorithms work?

Algorithm books spend a great deal of time on sorting algorithms. For example, my book Essential Algorithms: A Practical Approach to Computer Algorithms spends a full chapter describing different sorting algorithms. There are several reasons why sorting algorithms are so popular.

First, sorting is a common task in computer applications. Almost any data is more meaningful if you can sort it and display it in various ways.

Second, sorting algorithms demonstrate many important algorithmic techniques such as binary subdivision, recursion, and linear interpolation. Studying sorting algorithms will teach you techniques that you may be able to use in other parts of your applications.

Third, different sorting algorithms behave differently for different data so no single algorithm is best under all circumstances. Often Quicksort provides excellent performance, but under some circumstances Bubblesort or Countingsort can give you much better performance.

Finally complex algorithms are just plain fun! Okay, I admit I'm an algorithm nerd, but I think of these things as puzzles. It's more fun for me to get a complex algorithm working correctly than it is to work a Sudoku puzzle.

This series of posts describes several important sorting algorithms, including a Quicksort algorithm that is similar to the one used by Array.Sort. Depending on the circumstances, you can pick the algorithm that best suits your data.

Array.Sort

The Array class's Sort method sorts arrays very quickly. It's easy to use and you don't need to debug it, so I recommend that you start by using it and decide whether it is fast enough for your needs. If Array.Sort is fast enough, then you're done and you don't need to implement, debug, and maintain a more complicated algorithm. If you have performance problems and know something about your data that will let one of the other algorithms give you better performance, then you can implement a different algorithm.

The example program uses Array.Sort as a benchmark for the other algorithms. The following code shows how the program runs a test of the Array.Sort method.

// Sort with Array.Sort. private void btnArraySort_Click(object sender, EventArgs e) { RunAlgorithm(txtTimeArraySort, ArraySort); } // Run an algorithm. private delegate void Algorithm(int[] values); private void RunAlgorithm(TextBox time_textbox, Algorithm algorithm) { time_textbox.Clear(); Cursor = Cursors.WaitCursor; Refresh(); int num_trials = int.Parse(txtNumTrials.Text); // Prepare the data. PrepareData(); Stopwatch watch = new Stopwatch(); for (int trial = 0; trial < num_trials; trial++) { // Copy the unsorted data into the SortedValues array. Array.Copy(Values, SortedValues, NumItems); // Run the algorithm. watch.Start(); algorithm(SortedValues); watch.Stop(); } // Display the total time. time_textbox.Text = watch.Elapsed.TotalSeconds.ToString("0.00") + " sec"; // Verify that the algorithm worked. Verify(); Cursor = Cursors.Default; }

When you click the Array.Sort button, the button's event handler calls the RunAlgorithm method passing it an algorithm and the TextBox where it should display the elapsed time.

The next piece of code declares a delegate named Algorithm that represents a method that takes an array of integers as a parameter.

The RunAlgorithm method takes a TextBox and an Algorithm as parameters. It performs some setup and calls PrepareData to make the data that will be sorted.

The PrepareData method is relatively straightforward so it isn't shown here. It just generates random numbers as specified by the parameters you enter on the form. If the Sorted box is checked, the method sorts the data and then switches some items around to make "# Unsorted" of them be unsorted. Download the example and look at the code to see how it works.

Next the RunAlgorithm method performs the trials. For each trial the code copies the unsorted values into the SortedValues array and then calls the current algorithm to sort the SortedValues array.

The method finishes by displaying the total elapsed time.

Note that the timing is approximate. Many trials can even out small, random fluctuations, but for extremely fast tests such as sorting 5 items, the timing may not be very good. In most cases the results are reasonable, however, and you can use them to compare different algorithms so I'm not going to worry about more accurate timers.

The following code shows how the program responds when you click the Array.Sort button.

// Sort with Array.Sort. private void btnArraySort_Click(object sender, EventArgs e) { RunAlgorithm(txtTimeArraySort, ArraySort); }

This code simply calls RunAlgorithm, passing it the txtTimeArraySort TextBox and the ArraySort method to be tested. The code for the other algorithms is similar. Their event handlers just pass different result TextBox controls and algorithm methods.

The following code shows the ArraySort method.

// Sort with Array.Sort. private void ArraySort(int[] values) { // Sort. Array.Sort(values); }

This code simply calls the Array class's Sort method. Nothing could be simpler!

If you look closely at the picture at the top of this post, you'll see that Array.Sort beat Quicksort by a fair margin but was beaten by Countingsort. (Bubblesort and Selectionsort would have taken forever so I didn't run them on this data.)

It's important to note, however, that this test used 10,000 items with values between 0 and 10,000. Different algorithms perform differently with different kinds of data, so Array.Sort isn't always fastest. It's often fastest, however, and very easy to use, so it's a good first choice.

My next few posts describe the other algorithms in greater detail so you can learn when to use which algorithm.

Download the example to experiment with it and to see additional details.