MindStudy - MindStudy

Question:

Published on: 22 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.      n₁ ← q − p + 1
2.      n₂ ← r − q
3.      Create arrays L[1 . . n₁ + 1] and R[1 . . n₂ + 1]
4.      FOR i ← 1 TO n₁
5.            DO L[i] ← A[p + i − 1]
6.      FOR j ← 1 TO n₂
7.            DO R[j] ← A[q + j ]
8.      L[n₁ + 1] ← ∞
9.      R[n₂ + 1] ← ∞
10.    i ← 1
11.    j ← 1
12.    FOR k ← p TO r
13.         DO IF L[i ] ≤ R[ j]
14.                THEN A[k] ← L[i]
15.                        i ← i + 1
16.                ELSE A[k] ← R[j]
17.                        j ← j + 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

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

= ……….

……….

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

Let 2^k=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)