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.
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. n1 ← q − p + 1
2. n2 ← r − q
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 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.
# 
Fig: Splitting the List in a 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)
Write a C language function to find the in-order successor of the root of a binary tree.
What is linear searching?
What are the methodology for dialog design?
Write short notes on the following:
Discuss Analysis Modeling Concepts and Approaches
