Mergesort, Quicksort
Runtime performance: O(N log N)
How do they do it? They don't examine every item every time, e.g.
partitioning
Performance Comparison (Pentium III 997MHz):
Sort Type
Number of items
run time
Weiss's Insertion sort
35000
30.9 seconds
Weiss's Quicksort (recursive)
35000
2.78 seconds
Java Arrays.sort
35000
0.041 seconds
Real-world programming with Sorts
Three Guidelines
Never write your own sort. Use a sort routine from a
library, or find prewritten code.
Writing your own sort is a really bad idea. Someone else
has already done all the work, don't waste your time. Even if
you're a great programmer, yours won't be as fast.
See guideline #1.
In Java
Collections.sort(myList);
// sorts by "default ordering" Arrays.sort(myArray);
// sorts by "default ordering"
Collections.sort(myList, new
WidgetComparator()); //provide a custom ordering
Exercise This class
from a production Java application
would appear on the surface to violate rule 1 above.
(It has a "bubbleSort()" method.)
Study the code. What is the author trying to accomplish?
Did he really need to write his own sort? If so, explain why.
If not, discuss how he could have solved his problem without
writing his own sort.