4 ms·

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

by 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..."