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?

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

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