libc merge sort improvement

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

libc merge sort improvement

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