improvement to glibc merge sort

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

Hi All.
i am reposting again my proposed improvement to mergesort that i have posted 
in last june as no one replied to it.the change to mergesort as suggested 
improves two apsects:
1-alloacted 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 comparsion 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 decription of the modified mergesort:
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 unmerged elements of the two halves into H2.
4-the final step is to copy the temporary array of size n/2 intto 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:pointer to H1 first unmerged element of H1.
src2:pointer to H1 first unmerged element of H2.
dst: pointer to where next element to be merged in H2.

in fact the pointer src2 could never exceed the pointer dst:
at begininning of step3 number of remaining unmerged 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 unmerged elements from  H1 is also decreased by 
one(src++) .so number of unmerged elements of H1 is still equal to free 
placess 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 having if src1==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.
the speedup i have obtained using this change is 10%-20%.there is no 
trade-off for speed as main difference with original algorithm is in doing 
less  copying of elements. also code size overhead if fairly small; it 
consists of mostly in using two loops instead of one loop in original 
version.
I will not post any code with this mail as implementikng the change is quite 
straightforward.
could anyone comment on the idea?

best regards.

_________________________________________________________________
Testez Windows Live Mail Beta ! http://www.ideas.live.com/