Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!usc!merlin.usc.edu!nunki.usc.edu!jeenglis
From: jeenglis@nunki.usc.edu (Joe English)
Newsgroups: comp.lang.c
Subject: Re: Looking for portable sort algorithm
Keywords: C, sort algorithm, portable, wanted
Message-ID: <5217@merlin.usc.edu>
Date: 20 Sep 89 21:15:21 GMT
References: <1102@lakesys.UUCP> <3994@ncsuvx.ncsu.edu>
Sender: news@merlin.usc.edu
Reply-To: jeenglis@nunki.usc.edu (Joe English)
Distribution: na
Organization: University of Southern California, Los Angeles, CA
Lines: 56

jnh@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@nunki.usc.edu