Fast, stable sort used to sort geometries
It's adapted from Tim Peters's work on list sorting for Python. More details
Here is the C code on which this class is based:
This class was also greatly inspired by the Java7 TimSort by Josh Blosh, with the
difference that temporary memory is allocated as the
geometry list grows and reused throughout the execution of the application.
Usage : ListSort has to be instantiated and kept with the geometry list ( or
w/e it may have to sort) Then the allocate method has to be called to
allocate necessary tmp space needed for the sort. This should be called once
for optimal performance, but can be called several times if the length of the
Disclaimer : I was intrigued by the use of val >>> 1 in the Java7 Timsort
in place of val / 2 (integer division). Micro benching revealed that val >>> 1
is twice as fast as val / 2 in Java6 and has similar perf in Java7. The
following code uses val >>> 1 whenever a value needs to be divided by 2 and
rounded to its floor.