Course Content

Other Courses

Tribhuvan university > CSIT - 2065 Syllabus > Data Structures and Algorithms > Old Questions > 2072

Data Structures and Algorithms - Old Questions

Syllabus Notes Old Questions Unit Wise Questions Question Bank

9. Write an algorithm and C function for merge sort.

5 marks | Asked in 2072

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++;

        }

    }
    while(x<m)
    {
        A[k] = A[x];
        k++;
        x++;
    }
    while(y<r)
    {
        A[k] = A[y];
        k++;
        y++;
    }
    for(i=l;i<= r; i++)
    {
        A[i] = B[i]
    }
}