Re: new module "mpsort" for faster sorting

[Bruno Haible]

Jim Meyering wrote:
> When sorting records larger than a pointer, reduced data movement is
> likely to be the overriding factor: better use of cache.
> I.e., setting up the array of pointers costs just O(N) time and memory,
> but you save O(N log(N)) time in reduced data copying costs, because
> mpsort is swapping only pointers, whereas qsort swaps the entire (larger)
> records.

This is undoubtable.

My question is: Once you have switched from an array representation with
sizeof (element) > sizeof (void *) to an array representation with
sizeof (element) == sizeof (void *), you still have 3 ways to sort:

  a) with qsort and a comparison function that does
     int cmp (void **p, void **q) { return element_cmp (*p, *q); }

  b) with a mergesort implementation that looks like mpsort, but calls
       cmp (&ba, &bb)
     instead of
       cmp (ba, bb)
     and instead does the indirection in the comparison function:
     int cmp (void **p, void **q) { return element_cmp (*p, *q); }

  c) with the mpsort function as it is, and element_cmp as the comparison
     function.

Does the major speedup come from the transition a) -> b), or from the
transition b) -> c) ?

Bruno