Niko Schwarz <niko.schwarz at gmx.net> is still concerned about sentinels.

	> as Insertion Sort is a part
	> of many advanced sorting algorithms.
	
	i wrote "part" with reason.
	
I know about quicksort.
I am familiar with C.A.R.Hoare's original article (Computer Journal,
1961 I think).  I've read Sedgewick's PhD thesis (Stanford), his
Acta Informatica article, his books.  I've spoken with the inventor
of "quickersort".  I have read the Bentley & McIlroy article, where
they point out that many of the platitudes about quicksort are
actually wrong.  I have their code, which I have experimented with.
Indeed, I have made substantial improvements to it, getting further
speedups of up to 20%.  (And yes, playing with the insertion sort
phase was one of the ways I did this.)  I have designed several
quicksort variants myself, including a 4-way quicksort.

	A lot of sorting algorithms speed up when you use insertion sort
	below a certain level.  Quick sort, e.g.
	
Unfortunately, this turns out to be misleadingly phrased.
To start with, recall that already, when it was first invented,
Quicksort was known to be more expensive than merge sort.
The machine it was invented for had 256 words of main memory,
they had a couple of thousand numbers to sort, and quicksort
let them sort bigger blocks.

A correct way to phrase this is "there are some sorting algorithms
where it pays to switch over to a different method for small batches".
Insertion sort is not the best method to switch over to.  It is
simply not as bad as selection sort.

Much depends on the relative cost of
 - the main recursive code
 - the alternative algorithm you switch over to
 - the element comparisons you really care about.

Some books will tell you to leave the small batches unsorted in quicksort
and then run one insertion sort over the lot.  Bentley & McIlroy measured
it, and will tell you that for realistic applications it is better to sort
each small batch immediately.

WHEN YOU SORT THE SMALL BATCHES IMMEDIATELY THERE IS NO PLACE TO PUT
ANY SENTINEL.

Some books will tell you that a good batch size is 10 (or even more)
elements.  My measurements suggest that the optimum is fairly broad,
but 8 is about as good as it gets.

The thing is, for small batches, you can write inline code that uses
the optimal number of comparisons, or very nearly the optimal number.

The code gets bulkier, to be sure, but if you are sufficiently bothered
about speed to consider using sentinels, you'll find using optimal
sorting for small batches pays off even better.

OK, let's be really honest about this.  I've found ways of improving
insertion sort, while still keeping to the spirit of insertion sort,
which mean that you can push the batch sizes up as high as 80 and
still find it paying off.  My code does NOT rely on sentinels, or
at least, not on sentinels other than the given data.  "Batching"
helps more than "sentinels".

	> To continue, what if you have to sort an Array, which has a
	fixed size?
	
	Well, Richard, I'm not saying I want to apply all my techniques
	in every situation.
	
Yes, but what situations *can* you use it in?
- You can't use it to sort an Array
  (but Arrays have cheaper #at: and #at:put: than most collections,
   so if it's NOT an Array you're sorting, you're wasting a lot of time)
- You can't use it to sort an OrderedCollection of Strings, Dates, Times &c

Let's take the excellent book by Cormen, Leiserson, and Rivest.
They use "sentinels" in three cases that I know of:

(1) In their definition of merge.

    Unfortunately, this has the unpleasant property that you can't use
    their merge code in merge sort.
    And it doesn't really adapt very well to merging two files either.
    In short, the only thing it simplifies is the presentation in the
    book, and it doesn't simplify _that_ worth speaking of.

(2) In doubly linked lists.

    In fact, what they use is NOT a sentinel as I understand the term,
    but a "header node".  The thing which is especially important about
    it is that they do not use the key field, only the identity of the
    node.  It's putting a special "-infinity" or "+infinity" value in
    the key field which is the important thing about a sentinel to me.

    Unfortunately, putting the header node *inside* the list has some
    extremely unpleasant consequences.  Amongst others, there are now
    two different kinds of node in the same list, and there is now
    ONE node which is not fully initialised amongst a bunch of others
    which must be fully initialised.  (This drastically reduces the
    usefulness of static checking tools like SPlint, which can warn
    you about uninitialised variables.)
    
    The worst consequence is that it actually makes the code more
    complicated...

(3) In red-black trees.

    This is like the doubly linked list case.  What they actually have
    is a "boundary node" shared by all such trees, and they don't use
    the value in the node.  (So we have the same partly initialised
    partly not mess.)  What they do use is the colour in the node.
    This DOES make a couple of tricky cases a bit simpler, but not
    dramatically simpler, and it does make them a bit faster, but
    not dramatically faster.  However, it makes *every* leaf test
    slower, and on some machines makes everything a little bit slower,
    by "putting more pressure on the registers".

	geek! i had found out, and then modified my heap a little. now the array 
	performs downheap and upheap itself, from firstIndex to lastIndex.
	I think I'm faster than the default implementation in squeak. Do you have a 
	benchmark at hand? Or a typical piece of code accessing a heap?
	
I haven't used Heaps in Squeak yet.  Anyone else got a benchmark?

	>     For the fastest way to insertion sort an OrderedCollection in
	> Smalltalk: 1.  copy the elements into an Array (just the right size!)
	>     using array := oc asArray.
	>
	> 2.  sort the array using (the Smalltalk equivalent of) the C code isort()
	>     I displayed above.
	>
	> 3.  stuff the array back into the OrderedCollection.
	
	Why not placing the modifying code in the underlying array?
	sic, the underlying array is exactly the same as the oc, except
	that it has a head and a tail.  you could sort the underlying
	array from within the array, using sort from:  to:.

I'm having trouble understanding the way you said this, but I think I
get the idea.  If I've understood you correctly, the idea is to add
#isSorted, #isSortedBy:, #sort, #sort:
methods to OrderedCollection that mirror the methods in ArrayedCollection,
effectively by delegating to the underlying array.

Nice idea!  Expect a change set soon.

(#sort:to: is a private method of SortedCollection.
It isn't part of the Array protocol.)