You are here

Writing Mathlets III: A Call to Math Professionals - Basic Sorting

Tom Leathrum
My focus in this article is the geometry involved in deciding how to sort facets, but the sorting process itself presents some interesting problems as well. General sorting procedures have been studied extensively in computer science -- see especially Donald Knuth's The Art of Computer Programming, Vol. 2: Sorting and Searching --  and this is not an appropriate place for an extensive comparison of sorting techniques. But there is an interesting and important decision to be made here, so it is worth looking briefly at some of the possible sorting procedures.

The applet on this page shows a direct side-by-side comparison, a sort of "race," with three different sorting algorithms, Merge Sort, Insertion Sort, and Hoare's QuickSort. The list elements are represented as vertical lines of different lengths, from length 1 to length 100. When the applet initially loads, all of the lists are in sorted order, so you see what appear to be solid black triangles. When you click the "Randomize" button, the lists are scrambled pretty thoroughly, and all three methods are given the same scrambled list. When you click the "Start" button, all three methods begin sorting the list. Note here that QuickSort and Merge Sort perform just about equally well, with perhaps just a bit better performance from QuickSort. If you get tired of waiting for Insertion Sort to finish, click the "Stop" button.

The "Clear" button resets the applet to its initial state, with all three lists sorted. Now click the "Perturb" button in the applet. This does not thoroughly scramble the lists, but instead leaves nearly half of the list untouched, and the elements that are moved are generally not moved far in the list. Again, all three methods are given the same unsorted list. Click the "Start" button again. Note now that both QuickSort and Insertion Sort perform well.

The applet counts the numbers of basic operations each method performs when sorting the list: comparisons between two elements and swapping two elements. Actually, Merge Sort doesn't use swap operations as the other two do. It takes two adjacent, previously sorted segments of list and copies them into an external block of memory, merging the two sorted segments into a single sorted segment in the process. Then it copies the newly sorted segment back into the block occupied by the two original segments. So instead of counting the swapping operations, this method counts the operations of putting single elements back into the list, which gives a count consistent with the swap operations in the other methods.

Merge Sort is the algorithm provided in the Java libraries as part of the Java Collections Framework. The decision to provide this as the default sorting procedure is a sound one, since the method is generally efficient and its performance is consistent. However, during mouse rotations of a graph, as in the applet on page 2, the list of facets is generally not randomized, but rather only slightly perturbed, and, as seen on this page, the performance of Merge Sort can easily be beaten by other methods.

The Insertion Sort algorithm is a simple, some would say naïve, method: With a previously sorted initial segment, take the next element in the list, and swap it down into the sorted segment until it is in its appropriate place, then repeat until the entire list is sorted. It has generally poor performance, but it can have some surprisingly good results for lists that are only slightly perturbed, as seen in the applet on this page.  In fact, it can sometimes beat Merge Sort.

The QuickSort algorithm is more difficult to explain and understand, and its performance envelope has some potentially bad worst-case scenarios, but its typical performance is at least as good as, and often better than, Merge Sort. Indeed, the problems with QuickSort have more to do with how divisions are chosen for its divide-and-conquer strategy -- if the elements chosen for divisions of the unsorted list wind up consistently too far to one side of the sorted list, the performance suffers -- and even randomly chosen divisions keep good performance. Moreover, as is important for the graph rotations, QuickSort performs well on lists that are only slightly perturbed.

So the graphing applet on page 2 uses the QuickSort algorithm. For the list of 3200 facets, the sorting procedure typically takes no more than about 40,000 steps, significantly less for lists that are only slightly perturbed.

Tom Leathrum, "Writing Mathlets III: A Call to Math Professionals - Basic Sorting," Convergence (September 2005)