4 ms·

I thought Java's sorting algorithm was just recently replaced: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6804124 http://bugs.sun.com/bugdatabase/view_b

by dminor 17y ago

I thought Java's sorting algorithm was just recently replaced: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6804124 http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6804124 Is this the same, or something new?

btilly 17y ago
This is new. Java can use multiple sorting algorithms with different trade-offs. Merge sort algorithms have a good worst case scenario, but are somewhat slower in many average cases. They also need more memory. By contrast quick sort algorithms have very bad worst cases, but tend to be faster in the average case. The bug you pointed at was a replacement of Java's merge sort with a merge sort that does a better job of speeding up when it runs across runs of already sorted data. This is a replacement of quick sort with a variation that has better average running time. So what is the difference between a merge sort and a quick sort? Well both are divide and conquer algorithms. Merge sorts are based on splitting a list into two halves, sorting each half, then merging the two lists. Quick sorts are based on taking an element from a list called a pivot, then dividing the list into elements that are larger, smaller, or equal to the pivot. The larger and smaller lists are then sorted in turn. If you're clever about how you set things up you can do a quick sort in place, and this is faster than having to assign then free up memory. This algorithm is a variation on quick sort that uses 2 pivots rather than 1. The win over a traditional quick sort is that you can sort in place with the same number of comparisons and less moving of data around in memory. This is a win in two ways. First of all you do less moving data around. Possibly more important is the fact that if you're doing the same number of comparisons but swapping less often, then those comparisons have more predictable results. If you understand CPU architecture you'll note that this means fewer pipeline stalls, which really helps performance.

by dminor 17y ago

btilly 17y ago

This is new. Java can use multiple sorting algorithms with different trade-offs. Merge sort algorithms have a good worst case scenario, but are somewhat slower in many average cases. They also need more memory. By contrast quick sort algorithms have very bad worst cases, but tend to be faster in the average case. The bug you pointed at was a replacement of Java's merge sort with a merge sort that does a better job of speeding up when it runs across runs of already sorted data. This is a replacement of quick sort with a variation that has better average running time. So what is the difference between a merge sort and a quick sort? Well both are divide and conquer algorithms. Merge sorts are based on splitting a list into two halves, sorting each half, then merging the two lists. Quick sorts are based on taking an element from a list called a pivot, then dividing the list into elements that are larger, smaller, or equal to the pivot. The larger and smaller lists are then sorted in turn. If you're clever about how you set things up you can do a quick sort in place, and this is faster than having to assign then free up memory. This algorithm is a variation on quick sort that uses 2 pivots rather than 1. The win over a traditional quick sort is that you can sort in place with the same number of comparisons and less moving of data around in memory. This is a win in two ways. First of all you do less moving data around. Possibly more important is the fact that if you're doing the same number of comparisons but swapping less often, then those comparisons have more predictable results. If you understand CPU architecture you'll note that this means fewer pipeline stalls, which really helps performance.