Java Reference
In-Depth Information
static<EextendsComparable<?superE>>
voidmergesort(E[]A,E[]temp,intl,intr){
inti,j,k,mid=(l+r)/2;//Selectthemidpoint
if(l==r)return; //Listhasoneelement
if((mid-l)>=THRESHOLD)mergesort(A,temp,l,mid);
elseinssort(A,l,mid-l+1);
if((r-mid)>THRESHOLD)mergesort(A,temp,mid+1,r);
elseinssort(A,mid+1,r-mid);
//Dothemergeoperation.First,copy2halvestotemp.
for(i=l;i<=mid;i++)temp[i]=A[i];
for(j=1;j<=r-mid;j++)temp[r-j+1]=A[j+mid];
//Mergesublistsbacktoarray
for(i=l,j=r,k=l;k<=r;k++)
if(temp[i].compareTo(temp[j])<0)A[k]=temp[i++];
elseA[k]=temp[j--];
}
Figure7.10 Optimized implementation for Mergesort.
to act as a sentinel for the other. Unlike the previous implementation, no test is
needed to check for when one of the two subarrays becomes empty. This version
also uses Insertion Sort to sort small subarrays.
Analysis of Mergesort is straightforward, despite the fact that it is a recursive
algorithm. The merging part takes time (i) where i is the total length of the two
subarrays being merged. The array to be sorted is repeatedly split in half until
subarrays of size 1 are reached, at which time they are merged to be of size 2, these
merged to subarrays of size 4, and so on as shown in Figure 7.8. Thus, the depth
of the recursion is log n for n elements (assume for simplicity that n is a power
of two). The first level of recursion can be thought of as working on one array of
size n, the next level working on two arrays of size n=2, the next on four arrays
of size n=4, and so on. The bottom of the recursion has n arrays of size 1. Thus,
n arrays of size 1 are merged (requiring (n) total steps), n=2 arrays of size 2
(again requiring (n) total steps), n=4 arrays of size 4, and so on. At each of the
log n levels of recursion, (n) work is done, for a total cost of (n log n). This
cost is unaffected by the relative order of the values being sorted, thus this analysis
holds for the best, average, and worst cases.
7.5
Quicksort
While Mergesort uses the most obvious form of divide and conquer (split the list in
half then sort the halves), it is not the only way that we can break down the sorting
problem. And we saw that doing the merge step for Mergesort when using an array
implementation is not so easy. So perhaps a different divide and conquer strategy
might turn out to be more efficient?
Search WWH ::




Custom Search