It was invented by Tim Peters for Python, and has been the default there since 2.3. The Java runtime uses it to sort arrays of non-primitive type (that is, arrays of values that can be treated as Objects).
>Please note that O matters. Even if both algorithms belong to O(n log n) class, algorithm for which O=1 is 100 times faster then algorithm for which O=100.
Wait, what? O = 100? That's just... not how it works.
I think what the author meant was that the elapsed time to sort: t = k * O(f(n)). So given two algorithms that have the same O(f(n)) then the smaller the k, the faster the sort.
As far as I know, Quicksort cannot be implemented to be stable without an auxiliary array. So implementing Quicksort to be stable destroys the in-place feature.
If you want something in-place and stable, you'll have to use something like WikiSort [1] or GrailSort [2].
> Quicksort cannot be implemented to be stable without an auxiliary array
Okay, you need an additional array (I am using a separate array, the "result array") [1]: But that doesn't matter, since the additional array can just grow (while the partitions/other arrays shrink).
Though my implementation is not cache-aware, which is very interesting and pretty relevant for performance.
[1] Actually I am using a linked tree data structure: "In-place"... which IS HIGHLY relevant: It can occur that the input data is large ((already) filling up (almost) all RAM) and these programs ("Execution Groups") terminate "the old way", so just 'abend'.
And hence it stands: By the way I have proven that you can implement QuickSort STABLE AND IN-PLACE
Thank you :) and fix you wording, when saying "Quicksort is..."
>> Who the heck can say sth about the imput (that it may be like "pre-sorted" ?!)
Lots of real world (as opposed to synthetic random test data) may be already ordered or contain ordered subsequences. One wants to run a sorting algorithm to guarantee the data is sorted, and thus performance on pre-sorted data is important.
No. For radix sort this constant factor is quite low, so it outperforms std::sort in most cases.
Try sorting a million integers, my results are:
std::sort: 60 ms;
radix-sort (LSB, hand coded, less than 20 lines): 11 ms.
It gets even better when you mix MSB with LSB for better locality.
No, there are no problems with doubles or negative integers.
For sizeof(key_value)<=16 B (8 for key, 8 for pointer), radix is the best sort on desktop computers.
12 comments
[ 0.24 ms ] story [ 46.3 ms ] threadhttp://en.wikipedia.org/wiki/Timsort
OpenJDK implementation. Good notes in the comments:
http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/...
Wait, what? O = 100? That's just... not how it works.
> Among non-stable algorithms [...] quicksort [...]
QuickSort can be implemented so that it is stable: http://www.mqseries.net/phpBB2/viewtopic.php?p=273722&highli... (I am author, AMA)
Why is gnu-core-utils-sort implemented as mergesort (also in place, but slower) ?
Edit: And sorry: In-Place matters: Quicksort is fastest AND uses least memory.
Who the heck can say sth about the imput (that it may be like "pre-sorted" ?!)
If you want something in-place and stable, you'll have to use something like WikiSort [1] or GrailSort [2].
[1] https://github.com/BonzaiThePenguin/WikiSort
[2] https://github.com/Mrrl/GrailSort
Okay, you need an additional array (I am using a separate array, the "result array") [1]: But that doesn't matter, since the additional array can just grow (while the partitions/other arrays shrink).
Though my implementation is not cache-aware, which is very interesting and pretty relevant for performance.
[1] Actually I am using a linked tree data structure: "In-place"... which IS HIGHLY relevant: It can occur that the input data is large ((already) filling up (almost) all RAM) and these programs ("Execution Groups") terminate "the old way", so just 'abend'.
And hence it stands: By the way I have proven that you can implement QuickSort STABLE AND IN-PLACE
Thank you :) and fix you wording, when saying "Quicksort is..."
Lots of real world (as opposed to synthetic random test data) may be already ordered or contain ordered subsequences. One wants to run a sorting algorithm to guarantee the data is sorted, and thus performance on pre-sorted data is important.
This is why Timsort is the default sort in Python and Java. http://en.m.wikipedia.org/wiki/Timsort
It is the worst case performance for quick sort.
A factor of log(n) (or less) difference can often be overwhelmed for all practical inputs by a constant factor.
Try sorting a million integers, my results are: std::sort: 60 ms; radix-sort (LSB, hand coded, less than 20 lines): 11 ms. It gets even better when you mix MSB with LSB for better locality.
No, there are no problems with doubles or negative integers. For sizeof(key_value)<=16 B (8 for key, 8 for pointer), radix is the best sort on desktop computers.