Java Reference
In-Depth Information
static<EextendsComparable<?superE>>
voidmergesort(E[]A,E[]temp,intl,intr){
intmid=(l+r)/2; //Selectmidpoint
if(l==r)return; //Listhasoneelement
mergesort(A,temp,l,mid); //Mergesortfirsthalf
mergesort(A,temp,mid+1,r);//Mergesortsecondhalf
for(inti=l;i<=r;i++) //Copysubarraytotemp
temp[i]=A[i];
//DothemergeoperationbacktoA
inti1=l;inti2=mid+1;
for(intcurr=l;curr<=r;curr++){
if(i1==mid+1) //Leftsublistexhausted
A[curr]=temp[i2++];
elseif(i2>r) //Rightsublistexhausted
A[curr]=temp[i1++];
elseif(temp[i1].compareTo(temp[i2])<0)//Getsmaller
A[curr]=temp[i1++];
elseA[curr]=temp[i2++];
}
}
Figure7.9
Standard implementation for Mergesort.
input list alternating between the two sublists. The first element is assigned to the
first sublist, the second element to the second sublist, the third to first sublist, the
fourth to the second sublist, and so on. This requires one complete pass through
the input list to build the sublists.
When the input to Mergesort is an array, splitting input into two subarrays is
easy if we know the array bounds. Merging is also easy if we merge the subarrays
into a second array. Note that this approach requires twice the amount of space
as any of the sorting methods presented so far, which is a serious disadvantage for
Mergesort. It is possible to merge the subarrays without using a second array, but
this is extremely difficult to do efficiently and is not really practical. Merging the
two subarrays into a second array, while simple to implement, presents another dif-
ficulty. The merge process ends with the sorted list in the auxiliary array. Consider
how the recursive nature of Mergesort breaks the original array into subarrays, as
shown in Figure 7.8. Mergesort is recursively called until subarrays of size 1 have
been created, requiring log n levels of recursion. These subarrays are merged into
subarrays of size 2, which are in turn merged into subarrays of size 4, and so on.
We need to avoid having each merge operation require a new array. With some
difficulty, an algorithm can be devised that alternates between two arrays. A much
simpler approach is to copy the sorted sublists to the auxiliary array first, and then
merge them back to the original array. Figure 7.9 shows a complete implementation
for mergesort following this approach.
An optimized Mergesort implementation is shown in Figure 7.10. It reverses
the order of the second subarray during the initial copy. Now the current positions
of the two subarrays work inwards from the ends, allowing the end of each subarray
