Looking for portable sort algorithm

[Joe English]

jnh at ecemwl.UUCP (Joseph N. Hall) writes:

>On my VAXstation [the following code] sorts 10,000 integers in 
>22 seconds.  qsort takes about
>6 seconds.  (alas!)  ssort and qsort both take <1 second to sort 1,000
>integers.

[...]
>           for (
>               memcpy(K, Kj, size), Ki = Kj - hSize;
>               ((*compar)(K, Ki) < 0) && (Ki >= (char *) base);
>               Ki -= hSize
>           ) {
>               memcpy(Ki + hSize, Ki, size);
>           }
>           memcpy(Ki + hSize, K, size);
>       }
>   }

I achieved a speedup of > 30x by switching from
memcpy() to pointer swapping in my sort routine.
That's partly because the memcpy() on the system I was
working on was braindead, but I expect that (for large
sorts) the cost of allocating and building an array of
pointers becomes negligible compared to the gain
achieved by not using memcpy() regardless of the
implementation.

As long as we're on the subject of sorting, I was
wondering why the standard sort routine is implemented
as a quick-sort nearly everywhere, given its poor
worst-case behaviour.  Any guesses?

Also, I've found another sorting paradigm that's more
useful than the array sort in several cases:

	start_sort(comparison_function,sizeof_element);

	while ("there are more keys to be sorted")
	    add_key(&key);

	do_sort();

	while (retrieve_key(&key))
	    "do whatever you want with it."

This is especially good for database sorts, when you're reading from
secondary storage and the whole thing won't fit in memory.  The sort
package can retain as many keys as possible in a buffer, then sort and
dump them to a temporary file for later merge-sort if and when the
buffer fills up.


--Joe English

  jeenglis at nunki.usc.edu