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
