# Sorting Algorithms

We all know that Quicksort is one of the fastest algorithms for sorting. It's not often, however, that we get a chance to see exactly how fast Quicksort really is. The following applets chart the progress of several common sorting algorithms while sorting an array of data using in-place algorithms. This means that the algorithms do not allocate additional storage to hold temporary results: they sort the data in place. (This is inspired by the algorithm animation work at Brown University and the video Sorting out Sorting By Ronald Baecker from the University of Toronto (circa 1970!).)

Some of these sorts are very stupid or very slow and should not be used in code. The use of Bubblesort is deprecated. So don't use Bubblesort! Also, don't use Swapsort! It is only a demonstration of the amount of time Java takes to swap n elements.

In-Place Mergesort is yet another abomination. Mergesort is supposed to run in O(n log n), but the implementation here runs in O(n * n). This is because a temporary scratch array is not used. As with most of the examples here, In-Place Mergesort sorts the elements in the array without using additional storage (other than the stack used for the recursive calls, and temporary variables). Jack Snoeyink has provided me with a the Double Storage mergesort algorithm sort implementation that uses a scratch array.

New: Radix sort by Alvin Raj, August 13, 2002.

Click on each applet to see the algorithm run. Click on the name of the algorithm to see the source.
Bubble Sort (by James Gosling and Jason Harrison)

Bi-Directional Bubble Sort (by James Gosling)

Selection Sort (by Jason Harrison)

Shaker Sort (by Jason Harrison)

Insertion Sort (by Jason Harrison)

In-Place Merge Sort (by Jason Harrison)

Double Storage Merge Sort (by Jack Snoeyink)

Comb Sort 11 (by Jason Harrison)

Shell Sort (by Jason Harrison)

Heap Sort (by Jason Harrison)

Quick Sort (by James Gosling)

Quick Sort with Bubblesort (by Jim Boritz)

Enhanced Quick Sort (by Jim Boritz)

Fast Quick Sort (by Denis Ahrens)

Swap Sort (by Jason Harrison) This algorithm is broken. And it is not a sort! (Why it is broken is an exercise for the reader.)

The source code for the SortAlgorithm class and the SortItem class are available.

Sorting routines to be added when I have the time (aka possibly never):
• Three way merge.
• Quicksort with duplicated pivots.
• Random Swap sort.
• Bubblesort with early termincation.
• Quicksort that sorts the shorter list first.
• Quicksort that sorts lists of size < 30 with Insertion sort.
• Quicksort using Van Emden's exchange procedure for partitioning.
• Variants of Mergesort, including the "correct" method.
• Radix sorts. Done, thanks to Alvin Raj.
• Samplesort.
If you'd like to code any of those algorithms, please do and send me the code.

• Counting of element comparisons and element swaps.
• Counting of loop comparisons.
• Counting of recursive calls.
One of my favorite references to sorting routines is "Sorting" by William A. Martin, in ACM Computing Surveys, Volume 3, Number 4, December 1971, pages 147-174. The abstract reads:
The bibliography appearing at the end of this article lists 37 sorting algorithms and 100 books and papers on sorting published in the last 20 years. The ideas presented here have been abstracted from this body of work, and the best algorithms known are given as examples. As the algorithms are explained, references to related algorithms and mathematical or experimental analyses are given. Suggestions are then made for choosing the algorithm best suited to a given situation.

Disclaimer: If you use this page as part of your teaching, please let me know. I tend to refer students who ask too many questions back to their instructor. Requests for translations of the Java sources to other programming languages will be denied. This page was created in a fit of "thesis avoidance" in the summer of 1996.

Originally created by

James Gosling, jag@firstperson.com
And modified by
Jason Harrison, harrison@cs.ubc.ca
and
Jim Boritz, boritz@cs.ubc.ca

Thanks to Jean-Luc Duprat who rebuilt this page for Netscape 2.0 and recompiled the applets with the JDK.

Thanks to Guido Bunsen who put the applets into a table on this page

Peter Brummund is the author of The Complete Collection of Algorithm Animations if you're looking for more animated algorithms.

This is http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html.
Maintained by Jason Harrison (harrison@cs.ubc.ca).
accesses since November 4, 2001.