Thread overview |
---|
July 08, 2014 Quicksort Variants | ||||
---|---|---|---|---|
| ||||
After having read http://togototo.wordpress.com/2014/06/20/the-magic-forest-problem-revisited-rehabilitating-java-with-the-aid-of-d/ I stared at forest_t[] quickSort(forest_t[] fors) pure nothrow { if (fors.length >= 2) { auto parts = partition3!(forLessThan)(fors, fors[$ / 2]); parts[0].quickSort; parts[2].quickSort; } return fors; } for a while. Could somebody explain why this gave such a speed boost? To my knowledge it is an optimization which gives extra speedup when fors is already partially sorted right? Are there any plans to merge this optimization into existing or new sorting algorithms in Phobos? I recall that Python's default sorting algorithm is related to this, right? |
July 09, 2014 Re: Quicksort Variants | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | On Tuesday, 8 July 2014 at 20:50:01 UTC, Nordlöw wrote: > I recall that Python's default sorting algorithm is related to this, right? https://en.wikipedia.org/wiki/Timsort |
July 09, 2014 Re: Quicksort Variants | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | On Tuesday, 8 July 2014 at 20:50:01 UTC, Nordlöw wrote: Also related: http://forum.dlang.org/thread/eaxcfzlvsakeucwpxigd@forum.dlang.org#post-mailman.2809.1355844427.5162.digitalmars-d:40puremagic.com |
Copyright © 1999-2021 by the D Language Foundation