libc merge sort improvement

["djamel anonymous" <djam8193ah at hotmail dot com>]

Hi All.i am resending my last post on improvement on glibc msort routine.the 
reason for resend is mostly to correct some small typos errors that i made 
in last post.

the change to merge-sort as suggested improves two aspects:
1-allocated temporary array is of size n/2 instead of n.
2-copying at end of sort function is n/2 elements instead of n 
elements.overall the total extra copying is n/2*log(n) elements instead of 
n*log(n) elements.

similar changes were previously posted on this mailing list but were 
rejected because they didn't respect the following requirement of C 
standard: the comparison function must only be called with elements that are 
inside the original array(and not from temporary array for example).the 
proposed change respects this requirement.
here is a description of the modified merge-sort:
1-sort the two halves of the array.the first half H1 is of size n/2 and the 
second half H2 is of size n-n/2 .
2-merge elements from the two halves into the temporary array.as the 
temporary array is of size n/2 we will merge the k first elements from the 
H1 and the n/2-k first elements H2.
3-merge the remaining non merged elements of the two halves into H2.
4-the final step is to copy the temporary array of size n/2 into H1.

the step 3 is always correct as we will never overwrite any element of H2 
that have not been merged yet.we have three pointers:
src1:read pointer to first non merged element of H1.
src2:read pointer to first non merged element of H2.
dst: write pointer to where to merge next element(this pointer points into 
H2 as we merge elements into H2).

in fact the pointer src2 could never exceed the pointer dst:
at beginning of step3 number of remaining non merged elements in H1 
(H2-src1) is n/2-k which is the same as number of free places in H2 
(src2-dst).at each iteration of step 3 we will have two cases:
1-we merge one element from H1 .so number of free places is decreased 
(dst++) by one and number of non merged elements from H1 is also decreased 
by one(src++) .so number of non merged elements of H1 is still equal to free 
places in H2.so we have H2-src1==src2-dst.
2-we merge one element from H2 and we increment both src2 and dst.we still 
have H2-src1==src2-dst.

if at any time we have src2==dst we will also have src1==H2 which means that 
all element of H1 have been merged.so we can stop step 3 as all the 
remaining elements of H2 are already at their correct place.

i hope this time i will get at least some feedback.it is quite frustrating 
to spend time to think to solve a problem implement and test the solution to 
that problem .then spending time to send it to mailing list several times 
and at the end get no feedback.at least if people think that my solution has 
some problem or is not adequate, they could just answer to my post.obviously 
i don't see what's the problem with an idea that improves speed by 10%-20% 
and reduces space allocation by 50%.all with very modest increase in code 
size.

best regards.

_________________________________________________________________
MSN Hotmail : créez votre adresse e-mail gratuite & à vie ! 
http://www.msn.fr/newhotmail/Default.asp?Ath=f