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/ |
Free forum by Nabble | Edit this page |