World: r3wp

I ran into the problem when I was sorting words in a block and the 
bindings mattered.

If we want SORT to be stable, the implementation will have to abandon 
the use of qsort(3).

That would explain why the ticket is still not fixed. Please mention 
this in a ticket comment - it might lead to changing its status.

You can of course hack stability into qsort() by falling back to 
comparing adresses if values are the same.

Not sure if Carl likes that :)

That won't work, because we are comparing EQUAL? (maybe plus /case), 
not SAME?.

Does qsort take a comparison function? If so, it might be a error 
in that function.

I'm talking about the C side of things here.

Same here - a C function pointer.

Then I don't understand your EQUAL?/SAME? remark.

If two elements are EQUAL?, fall back to comparing their addresses 
in memory.

Won't work for linked lists, will work for arrays stored consecutively.

Sorry, missed that. Yes, qsort takes a callback used for comparison. 
Here's the decl:


void qsort(void *base, size_t nitems, size_t size, int (*compar)(const 
void *, const void*));

Sorry, I just got that you were talking about using <= instead of 
<.

My remark above was to the effect: if two elements are EQUAL? compare 
their INDEX? instead. This may sound ridiculous in context of REBOL's 
SORT, but it is no problem in C.

As the comparison callback gets pointers to the elements anyway.

I still think that you need to write this stuff in a ticket comment. 
Writing it here will have no effect - the ticket is where the real 
discussion happens, and I don't seem to understand your argument 
well enough in this case to paraphrase you there.

I'm writing already.

All :) intended, of course.

In any case, I find this channel more fruitful for interactive discussion.

True. But Carl won't see it.

BrianH <And not well enough documented either. I don't really know 
how /compare works, not completely.>

Comparators and the stable-sort trick (-1, 0 +1) are documented here 
in an old change log. It never made it into the dictionary for SORT:
    http://www.rebol.com/docs/changes-2-5.html#section-72

Documentation request referencing that link added here: http://curecode.org/rebol3/ticket.rsp?id=1793

Thanks :)

Re -1 0 1 - as far as I remember, I read somewhere about negative, 
0, positive?

That works too:

>> sort/compare [20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 
1] func [x y] [case [x < y [3] x = y [0] 'else [-4]]]
== [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]

Are we talking R2's sort or R3's sort here? I know for a fact that 
R2's sort is stable. Obviously you can't get a stable sort if you 
use a comparator function and you return a logic! value.

Also, the current "best" algorithm appears to be http://en.wikipedia.org/wiki/Timsort

We must focus on algos which are doing the fewer comarisons and are 
fast with data almost sorted (it's our common case).

in that sense, Timsort would be a good choice because it's unsing 
a combination of merge sort + insertion sort
merge sort = fewer comparisons.

insertion sort = the faster one on data already sorted and small 
subsets of data

yes looks pretty decent... a nice wrap up here:
http://corte.si/posts/code/timsort/index.html

http://www.rebol.org/ml-display-message.r?m=rmlVPRF

Funny, I've coded "bottom-up heapsort"  last night (improved version 
of heapsort).
I give the "clean" version.

heapify: func [s start len comp /local child sav][
	;-- search terminal leaf.
	child: start
	while [2 * child < len][
		child: 2 * child
		unless (comp s/(++ child) s/:child) [-- child]
	]
	if 2 * child = len [child: len]

	;-- bottom-up, search insertion point
	while [comp s/:child s/:start][child: shift child -1]
		
	;-- bottom-up swap
	sav: s/:start
	while [child > start][
			s/:child: also sav sav: s/:child
			child: shift child -1
	]
	s/:child: sav
]

heapsort: func [serie comp /local len][
	len: length? serie
	;-- build heap
	for i shift len -1 1 -1 [heapify serie i len :comp]
	;-- sort
	for i len 1 -1 [
		swap serie at serie i
		heapify serie 1 i - 1 :comp
	]
	serie
]

>> heapsort serie func [a b][a < b]

Is it stable, Steeve?

>> heapsort [5 1 2 4] :lesser?
== [1 2 4 5]

, while

>> heapsort [5 1 2 4] :lesser-or-equal?
** Script error: cannot compare none! with integer!
** Where: comp while heapify for heapsort
** Near: comp s/:child s/:start

, is that intended?

Mindblock

a: "testing"

foreach v [ a ] [  .... ]

in .. .how to test if v is an empty? string?

don't you mean:

foreach v reduce [a] [if all [string? :v empty? :v] [...]...]

I didn't want to reduce first as then I can't report which one is 
empty?

I do not understand

say I have a: "testing" b: ""

how would I say .. variable b is empty?

If I reduce the block of words first, then I no longer know which 
word is empty

if you have foreach v [a] [...] , then v is a word, not a string, 
so, in case you really mean it, you need something like:

if all [string? get v empty? get v]

sounds right

thanks

Ladislav, I corrected the issue with :less-or-equal?
And made some optimizations (I hope so).
On large serie

heapify: func [s start len comp /local step sav inc][
	inc: 0
	
	;-- search terminal leaf.
	step: start
	while [2 * step < len][
		++ inc
		step: 2 * step
		unless (comp s/(++ step) s/:step) [-- step]
	]
	if 2 * step = len [++ inc step: len]

	;-- bottom-up, search insertion point
	loop inc [
		unless (comp s/:step s/:start) [break] 
		step: shift step -1
		-- inc
	]
	
	;-- bottom-up swap
	switch/default inc [
		1 [swap at s start at s step]	;-- single swap
		0 []							;-- no swap
	][
		sav: s/:start					;-- chain swap
		loop inc [
				s/:step: also sav sav: s/:step
				step: shift step -1
		]
		s/:step: sav
	]
]

heapsort: func [serie comp /local len][
	len: length? serie
	
	;-- build heap
	for i shift len -1 1 -1 [heapify serie i len :comp]
	
	;-- sort
	for i len 1 -1 [
		swap serie at serie i
		heapify serie 1 i - 1 :comp
	]
	serie
]

s: make block! len: 1000
loop len [append s random len]
s2: copy s

n: 0
heapsort s func [a b][++ n a < b]
print ["bottom-up heapsort, number of comparisons =" n]

n: 0
sort/compare s2 func [a b][++ n a < b]
print ["Rebol sort (R3 + Vista), number of comparisons =" n]

bottom-up heapsort, number of comparisons = 10301
Rebol sort (R3 + Vista), number of comparisons = 12726

Steeve, my measurements suggest, that your previous version was a 
bit faster (is it caused by the fact, that you have to provide also 
for :lesser-or-equal?