• =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (18/18) Jul 08 2014 After having read
• =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (2/4) Jul 09 2014 https://en.wikipedia.org/wiki/Timsort
• =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (3/3) Jul 09 2014 On Tuesday, 8 July 2014 at 20:50:01 UTC, Nordlöw wrote:

=?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:

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?

=?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:

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

=?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:

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