Duck Typing QuickSorts
##Duck Typing QuickSorts Tony Hoare's QuickSort was considered quick in 1962. But it was not because it has 0(n log n) average performance. Merge sorting was already established [Knuth credits Von Neumann in 1945] and has better worst case performance than QuickSort.
What made QuickSort a quick sort was it's space efficiency. Hoare's insight was in-place sorting. QuickSort was quicker because in-place sorting meant more blocks could be read from tape into fast memory on each IO cycle [and likewise written]. The speed improvement came from reduced latency. Because IO then as now was so much slower than fast memory, the practical performance improvement on non-trivial data was massive.
It's common to illustrate functional programming using a double filter for the pivot and to call it a "quicksort". These necessarily avoid inplace mutations.
Consider this page of examples in Python. If you consider the Python examples to be quicksorts, then clearly the code under review is a quicksort. If you don't then...
Garbage Out
##Garbage Out BecauseBecause the Java manages memory deallocation via garbage collection; because the JVM offers just-in-time compilation that may perform arbitrary optimizations of the bytecode, and different ones at different times based on how much time it has due to what else is running; and because modern CPU's utilize multiple levels of caching, simple definitions of "in place" become increasingly brittle the more absolute our definition of "true quicksort" becomes. Welcome to the effects of post modernism in computing.
Practical Improvement
##Practical Improvement
IssuesIssues of truth aside, the performance of QuickSort degrades toward worst case 0(n^2) if the data is sorted in reverse order. Hoare advised selecting the pivot at random rather than sequentially. That is randomly selecting the pivot from the interval [i, j] makes worst case performance statistically unlikely for any interestingly sized data. Of course, if the data source is known to be random then it's a waste of time. On the other hand, in the real world many data sources aren't random.
Final Remarks
###Final Remarks ThereThere are many sound insights in the other code reviews, and there's no point in chewing the same ground.
##Duck Typing QuickSorts Tony Hoare's QuickSort was considered quick in 1962. But it was not because it has 0(n log n) average performance. Merge sorting was already established [Knuth credits Von Neumann in 1945] and has better worst case performance than QuickSort.
What made QuickSort a quick sort was it's space efficiency. Hoare's insight was in-place sorting. QuickSort was quicker because in-place sorting meant more blocks could be read from tape into fast memory on each IO cycle [and likewise written]. The speed improvement came from reduced latency. Because IO then as now was so much slower than fast memory, the practical performance improvement on non-trivial data was massive.
It's common to illustrate functional programming using a double filter for the pivot and to call it a "quicksort". These necessarily avoid inplace mutations.
Consider this page of examples in Python. If you consider the Python examples to be quicksorts, then clearly the code under review is a quicksort. If you don't then...
##Garbage Out Because the Java manages memory deallocation via garbage collection; because the JVM offers just-in-time compilation that may perform arbitrary optimizations of the bytecode, and different ones at different times based on how much time it has due to what else is running; and because modern CPU's utilize multiple levels of caching, simple definitions of "in place" become increasingly brittle the more absolute our definition of "true quicksort" becomes. Welcome to the effects of post modernism in computing.
##Practical Improvement
Issues of truth aside, the performance of QuickSort degrades toward worst case 0(n^2) if the data is sorted in reverse order. Hoare advised selecting the pivot at random rather than sequentially. That is randomly selecting the pivot from the interval [i, j] makes worst case performance statistically unlikely for any interestingly sized data. Of course, if the data source is known to be random then it's a waste of time. On the other hand, in the real world many data sources aren't random.
###Final Remarks There are many sound insights in the other code reviews, and there's no point in chewing the same ground.
Duck Typing QuickSorts
Tony Hoare's QuickSort was considered quick in 1962. But it was not because it has 0(n log n) average performance. Merge sorting was already established [Knuth credits Von Neumann in 1945] and has better worst case performance than QuickSort.
What made QuickSort a quick sort was it's space efficiency. Hoare's insight was in-place sorting. QuickSort was quicker because in-place sorting meant more blocks could be read from tape into fast memory on each IO cycle [and likewise written]. The speed improvement came from reduced latency. Because IO then as now was so much slower than fast memory, the practical performance improvement on non-trivial data was massive.
It's common to illustrate functional programming using a double filter for the pivot and to call it a "quicksort". These necessarily avoid inplace mutations.
Consider this page of examples in Python. If you consider the Python examples to be quicksorts, then clearly the code under review is a quicksort. If you don't then...
Garbage Out
Because the Java manages memory deallocation via garbage collection; because the JVM offers just-in-time compilation that may perform arbitrary optimizations of the bytecode, and different ones at different times based on how much time it has due to what else is running; and because modern CPU's utilize multiple levels of caching, simple definitions of "in place" become increasingly brittle the more absolute our definition of "true quicksort" becomes. Welcome to the effects of post modernism in computing.
Practical Improvement
Issues of truth aside, the performance of QuickSort degrades toward worst case 0(n^2) if the data is sorted in reverse order. Hoare advised selecting the pivot at random rather than sequentially. That is randomly selecting the pivot from the interval [i, j] makes worst case performance statistically unlikely for any interestingly sized data. Of course, if the data source is known to be random then it's a waste of time. On the other hand, in the real world many data sources aren't random.
Final Remarks
There are many sound insights in the other code reviews, and there's no point in chewing the same ground.
##Duck Typing QuickSorts Tony Hoare's QuickSort was considered quick in 1962. But it was not because it has 0(n log n) average performance. Merge sorting was already established [Knuth credits Von Neumann in 1945] and has better worst case performance than QuickSort.
What made QuickSort a quick sort was it's space efficiency. Hoare's insight was in-place sorting. QuickSort was quicker because in-place sorting meant more blocks could be read from tape into fast memory on each IO cycle [and likewise written]. The speed improvement came from reduced latency. Because IO then as now was so much slower than fast memory, the practical performance improvement on non-trivial data was massive.
It's common to illustrate functional programming using a double filter for the pivot and to call it a "quicksort". These necessarily avoid inplace mutations.
Consider this page of examples in Python. If you consider the Python examples to be quicksorts, then clearly the code under review is a quicksort. If you don't then...
##Garbage Out Because the Java manages memory deallocation via garbage collection; because the JVM offers just-in-time compilation that may perform arbitrary optimizations of the bytecode, and different ones at different times based on how much time it has due to what else is running; and because modern CPU's utilize multiple levels of caching, simple definitions of "in place" become increasingly brittle the more absolute our definition of "true quicksort" becomes. Welcome to the effects of post modernism in computing.
##Practical Improvement
Issues of truth aside, the performance of QuickSort degrades toward worst case 0(n^2) if the data is sorted in reverse order. Hoare advised selecting the pivot at random rather than sequentially. That is randomly selecting the pivot from the interval [i, j] makes worst case performance statistically unlikely for any interestingly sized data. Of course, if the data source is known to be random then it's a waste of time. On the other hand, in the real world many data sources aren't random.
###Final Remarks There are many sound insights in the other code reviews, and there's no point in chewing the same ground.