Answer to Question #156802 in Databases | SQL | Oracle | MS Access for Josh

Question

1. An array A[0..n-1] is sorted using the merge-sort algorithm. The worst case and the best case running time of this computation respectively are

a. O (n) and O (n log n)

b. O (n log n) and O (n)

c. O (n log n) and O (n log n)

d. O (n2) and O (n log n)

Answer 1

Given,

Array is A[0..n-1]

Size of the array = n

Now, in the merge sort, array split into two equal half, and then sort this array individually.

This array will divide into two two half. Let the divided node is represented as A[L,R]. Let the splitting node be A[L, M] and A[M+1, R] and again we can take it as A[R-L+1]

As here array size is n, so splitting and merging can be done in $n+\frac{2\times n}{2}=2n$

Total running time of the merge sort $S=2\Sigma_{i=0}^{n-1}{2^i\frac{n}{2^i}}$

if i =n, then