Data Structures and Algorithms - Old Questions
13. Discuss merge sort. How you rate this sorting from selection sort?
Answer
AI is thinking...
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++;
}