Sorting ends of Voronoi diagram edges.

[tomilov]

There is a Voronoi diagram. For compactly located cloud of points it looks like this: As you can see it is a simple graph. A set of connected edges, which not corss each other. Some of them are rays (on the periphery), another ones are sections (also it is possible a strait line case, but it is not too interesting corner case). x-coordinate of the begins of the edges have the following distribution (in order of construction of them by Fortune's algorithm): Corresponding distribution for ends is here: I.e. it is almost sorted set of objects. They are almost not sorted in a strip of almost constant height. There are a small subset of overshoots.

Does vergesort suitable for such a distribution?

Is there good precalc for data, to ease a work for some classic sorting algorithm?

[Morwenn]

Looking at your distributions, it looks like an Inv-adaptive or Rem-adaptive sorting algorithm would be better: vergesort works well when there are runs bigger than n / log n in the collection to sort, where n is the size of the collection to sort. In your case, while the distributions look mostly sorted, the sorted runs don't always look big enough. The main feature of these distributions does not seem to be "big sorted runs", but "few misplaced elements". For such a case an algorithm like drop-merge sort is probably more suitable than vergesort.

[tomilov]

@Morwenn Thank you.

[Morwenn]

No problem. Your Voronoi diagram is pretty by the way :3