Path: utzoo!dciem!array!colin
From: colin@array.UUCP (Colin Plumb)
Newsgroups: comp.lang.c
Subject: Re: Sorting Algorithm
Keywords: Sort Sorting C Source Linked-Lists
Message-ID: <586@array.UUCP>
Date: 24 Aug 90 20:50:27 GMT
References: <wayned.0932@wddami.spoami.com>
Organization: Array Systems Computing, Inc., Toronto, Ontario, CANADA
Lines: 51

Binary insertion sorts are known.  They are close to
minimum-comparison, but are O(n^2).  Your linked list implementation
traverses, half of the sorted list to find the node to make the first
comparison with, a quarter for the seocnd comaprison, etc., all
traversals being linear.  The total is the length list, or twice the
amount of traversal for a linear insertion sort, but with many fewer
comparisons.

A more usual implementation uses an array, which requires constant
time to do each comparison, for a total of log N to find where the
node goes, but has linear insert time.

There are data structures that allow O(log N) insertion and O(log N)
retrieval of the k'th element, which would make this log N * log N
per node (for N * log N * log N total), but it's simpler just to
use heapsort or something.

From memory: (arrays are 0-based, bottom is a valid element, I'm sure
you can optimize the tail calls and things)

void siftdown(int array[], int top, int bottom)
{
	int next = 2*top+1;

	if (next > bottom)
		return;
	if (next < bottom && array[next+1] > array[next])
		next++;
	if (array[next] > array[top]) {
		int temp = array[next];
		array[next] = array[top];
		array[top] = temp;
		siftdown(array, next, bottom);
	}
}

void heapsort(int array[], int bottom)
{
	int i;
	for (i = bottom/2; i > 0; --i) {
		siftdown(array, i, bottom);
	}
	for (i = bottom; i > 0; --i) {
		int temp = array[i];
		array[i] = array[1];
		array[1] = temp;
		siftdown(array, 1, i-1);
	}
}
-- 
	-Colin