Sorting Algorithms

The animations on this page illustrate a number of different sequential and parallel sorting algorithms. The relative execution times of the animations give a very rough idea of the relative speeds of the algorithms. Each algorithm is finished when its colored lines disappear.

Speed and Efficiency Analysis.

• Bubble Sort is a sequential algorithm, with an average case time of O(n²).
• Quick Sort is a sequential algorithm, with an average case time of O(n log n).
• Odd-Even Transposition Sort is a parallel algorithm, with an worst case time of O(n), running on n processors. Its absolute speed up is O(log n), so its efficiency is O((log n)/n).
• Shear Sort is a parallel algorithm, with an worst case time of O(n^1/2 log n), running on n processors. Its absolute speed up is O(n^1/2), so its efficiency is O(1/n^1/2).

Java Implementation Notes

All the implementations are subclasses of the class SortAlgorithm, which uses the class SortItem. Both of these classes were designed and implemented by James Gosling, who also implemented Bubble Sort and Quick Sort.

My implementation of Shear Sort requires a minor modification to SortAlgorithm and SortItem.