3 ms·

> Among complex algorithms Mergesort is stable > Among non-stable algorithms [...] quicksort [...] QuickSort can be implemented so that it is stable: http://w

> Among complex algorithms Mergesort is stable > Among non-stable algorithms [...] quicksort [...] QuickSort can be implemented so that it is stable: http://www.mqseries.net/phpBB2/viewtopic.php?p=273722&highlight=#273722 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" ?!)

abetusk 12y ago
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]. [1] https://github.com/BonzaiThePenguin/WikiSort https://github.com/BonzaiThePenguin/WikiSort [2] https://github.com/Mrrl/GrailSort https://github.com/Mrrl/GrailSort
- mqsiuser 12y ago
  > 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..."
wffurr 12y ago
>> 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. This is why Timsort is the default sort in Python and Java. http://en.m.wikipedia.org/wiki/Timsort http://en.m.wikipedia.org/wiki/Timsort It is the worst case performance for quick sort.

abetusk 12y ago

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]. [1] https://github.com/BonzaiThePenguin/WikiSort https://github.com/BonzaiThePenguin/WikiSort [2] https://github.com/Mrrl/GrailSort https://github.com/Mrrl/GrailSort

mqsiuser 12y ago
> 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..."

wffurr 12y ago

>> 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. This is why Timsort is the default sort in Python and Java. http://en.m.wikipedia.org/wiki/Timsort http://en.m.wikipedia.org/wiki/Timsort It is the worst case performance for quick sort.