img
Question:
Published on: 3 December, 2024

Explain the mergesort algorithm.

Why does it run faster than bubble sort in most of the cases ? Show how the mergesort algorithm will sort the following array in increasing order :

100, 90, 80, 70, 60, 50, 40, 30, 20.

Analyses the time complexity of the mergesort algorithm.

 

Answer:

Merge sort is based on the divide-and-conquer paradigm.

Algorithm: Merge Sort

To sort the entire sequence A[1 .. n], make the initial call  to the procedure MERGE-SORT (A, 1, n).

MERGE-SORT (A, p, r)

1.     IF p < r                                                        // Check for base case
2.         THEN q = FLOOR[(p + r)/2]                 // Divide step
3.                 MERGE (A, p, q)                            // Conquer step.
4.                 MERGE (A, q + 1, r)                      // Conquer step.
5.                 MERGE (A, p, q, r)                        // Conquer step.

 

The pseudocode of the MERGE procedure is as follow:

MERGE (A, p, q, r )

1.      n1qp + 1
2.      n2rq
3.      Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
4.      FOR i ← 1 TO n1
5.            DO L[i] ← A[p + i − 1]
6.      FOR j ← 1 TO n2
7.            DO R[j] ← A[q + j ]
8.      L[n1 + 1] ← ∞
9.      R[n2 + 1] ← ∞
10.    i ← 1
11.    j ← 1
12.    FOR kp TO r
13.         DO IF L[i ] ≤ R[ j]
14.                THEN A[k] ← L[i]
15.                        ii + 1
16.                ELSE A[k] ← R[j]
17.                        jj + 1

# Time complexity of bubble sort in best case is O(n).But in average case and worst case is O(n^2). In merge sort time complexity is O(nlogn) in all cases, ie merge sort run faster than bubble sort in most of the cases.

#   merge sort splitting                                                                                                                    

Fig: Splitting the List in a Merge Sort

 

merging in merge sort

Fig: Lists as They Are Merged Together

 

Analysis of Time complexity:

In the merge sort , the call of the merge sort and merging does not depends on the order of the elements of the array. So the best case , average case and worst case time complexity are same in case of merge sort.

Now let total T(n) time is needed to sort the array. Here we are dividing the array into two equal sub part , each having n/2 elements.

So, T(n) = T(n/2) + T(n/2) + c.n [n>1]

       T(n) = 2T(n/2) + c.n

              = 2[2T(n/4) + c.n/2 ] + c.n

    = 22T(n/22) + 2.c.n

    = ……….

       ……….

      T(n) = 2kT(n/2k) + k.c.n

 

Let 2k=n , so k= log(n)

T(n)= n T(1) + c. n. log(n)

= n + c. nlog(n) for n=1,T(1)=1

So, T(n) =O(nlogn)


 


 

Random questions