[patch] sort and group case labels

[Joern Rennecke]

> It is _worst_case_ O(N^2) but in practice it is O(N log N).
> (And quicksort is typically faster than algorithms with a worst-case 
> O(N log N) time complexity).

+         for (i = 0; i < old_size - 2; i++)
+           {
+             tree base_case, base_high, base_label, type;
+ 
+             base_case = TREE_VEC_ELT (old_labels, i);
+             if (! base_case)
+               abort ();
+ 
+             type = TREE_TYPE (CASE_LOW (base_case));
+             base_label = CASE_LABEL (base_case);
+             base_high = CASE_HIGH (base_case) ?
+               CASE_HIGH (base_case) : CASE_LOW (base_case);
+ 
+             for (j = i; j < old_size - 2; j++)

That looks solidly O(n^2) to me.

> 
> I had an implementation before this one that would build an AVL tree,
> but using qsort turned out to be faster for a gcc bootstrap.
> Actually I tried quicksort because rth suggested that.  When I asked
> if that wouldn't be too slow, he asked back if that was sarcasm, so I
> decided to just try and see...

case labels often come pre-sorted, so here you are relying on using a qsort
implementation that uses a strategy that avoids pathological behaviour on
sorted input. (e.g. 'mid-array value is pivot' or 'look at values of start,
mid-array and end value, and pick the middle one for the pivot' .)