Data Structures and Algorithms - Old Questions
13. Discuss merge sort. How you rate this sorting from selection sort?
The basic concept of merge sort is divides the list into two smaller sub-lists of approximately equal size. Recursively repeat this procedure till only one element is left in the sub-list. After this, various sorted sub-lists are merged to form sorted parent list. This process goes on recursively till the original sorted list arrived.
Procedure
To sort A[l………….r]
1. Divide step: If a given array A has zero or one element, simply return; it is already sorted. Otherwise split A[l……….r] into two sub-arrays A[l………q] and A[q+1…………r] each containing about half of the element A[l…….r]. that is q is the half of way point of A[l…….r].
2. Conquer step: Sorting the two sub-arrays A[l………q] and A[q+1…………r] recursively. When the size of sequence of is 1 there is nothing more to do.
3. Combine step: combine the two sub-arrays A[l……q] and A[q+1…………r] into a sorted sequence.
C function
MergeSort(A, l, r)
{
If ( l < r)
{
m = (l + r)/2
MergeSort(A, l, m)
MergeSort(A, m + 1, r)
Merge(A, l, m+1, r)
}
}
Merge(A, B, l, m, r)
{
x=l, y=m;
k=l;
while(x<m && y<r)
{
if(A[x] < A[y])
{
B[k]= A[x];
k++;
x++;
}
else
{
B[k] = A[y];
k++;
y++;
}