Re: Hamming minigolf post mortem

On Sun, Apr 20, 2003 at 04:41:39PM +0300, Juho Snellman wrote:
> On Sun, Apr 20, 2003 at 01:03:06AM -0400, Ronald J Kimball wrote:
> > sort { $a > $b } @list doesn't even work reliably when you're only
> > interested in the smallest element.  Consider sorting a list containing two
> > elements, 1 and 3.  The outcome will depend on which value is used as $a
> > and which as $b.  3 > 1 will return 1, and the result will be (1, 3).  1 >
> > 3, however, will return 0, and the result could be either (1, 3) or (3, 1)!
> 
> It works reliably in the context of 5.8.0. Try it out! (I tested with
> a shuffled array of two million elements before deciding that it wasn't
> just a fluke).

Wow, you really tried this out!
My considerations that it could work were threefold:
1) I only need the smallest number anyway, so complete sorting is
   actually irrelevant
2) in fact, I don't really want to sort a list, but to merge two sorted
   lists: @s (presuming it stays sorted over iterations),
   and 2*$n,3*$n,4*$n,5*$n
   So I'm not dealing with an arbitrary list, which could make it easier
   for the sorting algorithm to sort it anyhow.
3) a sorting algorithm needs the comparison function for deciding
   whether to swap two elements, so somehwere it will contain code like
      @a[$i,$j] = @a[$j,$i] if ((elements must be swapped))
   In many sorting algorithms this will consistently be called for
   indices such that $i < $j; then the condition is just
      &compare($a[$i], $a[$j]) > 0
   This certainly holds for merge sort, which is one of the two
   algorithms Perl uses. When using quick sort, it depends very much on
   how it picks a medan and splits the list in two.
   
Can anyone with more knowledge of sorting or the innards of Perl shed
more light on this?

-- 
Daniël Tuijnman                                          Frodo failed
[email protected]                                  Bush has the ring