More about the design and analysis of Algorithms

Is Insertion Sort fast enough ?





















Divide - and - Conquer Algorithm
Now, running an organisation is no easy task. Planning, forecasting, monitoring, controlling, handling the finances, allocation of man-power and resources. There are a lot of things to be done. But no single individual does all the stuff by himself. An organisation has a strucutre. There is division of labour amongst the employees of the organisation. Thus, we break down a complex task into a number of sub-tasks.

So, when you can't do the whole, chop it off into small parts, and tackle those individually. If a particular part is still big enough, we further decompose it into smaller sub-parts. This is the core idea behind divide and conquer approach.

• Divide - Divide the given problem into sub-problems.
• Conquer - Solve the sub-problems if they are small enough, or divide them recursively.
• Combine - Combine the solutions of the sub-problems to construct the original solution.

Merge Sort Algorithm

• Divide the unsorted array into two sub-arrays of size n/2.
• Recursively sort the two sub-sequences using Merge Sort.
• Merge the two sorted sub-sequences to produce the final array.

The key sub-routine here is the Merge Sub-routine...

void merge(int A[], int low, int high, int mid)
{
int n1,n2,i,j,k;
int L[20],R[20];

n1 = mid - low + 1;
n2 = high - mid;

for(i=0 to n1;i++)
L[i] = A[low+i];

for(j=0 to n2;j++)
R[j] = A[mid+1+j];

for(i=0,j=0,k=low to high,i less than n1,j less than n2;k++){
if(L[i] less than R[j]){
A[k] = L[i++];
}
else{
A[k] = R[j++];
}
}

while(i less than n1)
A[k++] = L[i++];
while(j less than n2)
A[k++] = R[j++];

}

In each individual step, we look at the two elements in the list L[] and R[] and find the smaller of the two, and advancing the pointers into the array, so that I know what the current head of that list is.

The while loop that runs from p to r, defines the loop invariant. At any point k in the algorithm, A[p...k-1] is always sorted. We can use this loop invariant to prove the correctness of the algorithm. As you can see, the merge sub-routine takes theta(n) time.

Merge Sort will now be performed as follows :

void mergesort(int a[], int low, int high) {
int mid;
if(low less than high)
{
mid=(int)(low+high)/2;
mergesort(a,low,mid); mergesort(a,mid+1,high); merge(a,low,high,mid);
}
}

Analysing Merge Sort

























Recursion Tree for 2T(n/2)+cn
Well, let us build a recursion tree for the recurrence T(n)=2T(n/2)+cn which is a more explicit representation of the recurrence we want to solve...






Thus, the Merge Sort algorithm is asymptotically faster than Insertion Sort...!