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)
Define the ADT for stack. Show the implementation of the stack data structure using linked list.
Construct an AVL tree using the below list. Show all the steps 12, 11, 13, 10, 09, 15, 14, 18, 7, 6, 5.
Write a C language function to find the in-order successor of the root of a binary tree.
Write short notes on:
Explain left factoring with suitable example.
Write a C program to find the GCD of two numbers.
Discuss the different stages of ‘Capability Maturity Model’.
Write short notes on: