improvement to glibc merge sort

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

improvement to glibc merge sort

djamel anonymous
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/