Subject: Computer Algorithms 3) Design an efficient algorithm that sorts an arra
ID: 3864055 • Letter: S
Question
Subject: Computer Algorithms
3) Design an efficient algorithm that sorts an array containing 2 sorted sets of numbers, such as A=[3,4,7,9,13,1,5,6,8] (Note that [3,4,7,9,13] and [1,5,6,8] are both sorted, but A is not). Your algorithm declaration should look like this:
MYSORT(A,p,n)
where A is the input array, p is the index to the first element of the second set of numbers, and n is the length of array A.
Calculate the asymptotic running time and space of you algorithm.
Reference book
Introduction to Algorithms 3rd edition
Ebook URL:
http://ce.bonabu.ac.ir/uploads/30/CMS/user/file/115/EBook/Introduction.to.Algorithms.3rd.Edition.Sep.2010.pdf
Explanation / Answer
Mergesort is a sort algorithm that splits the item to be sorted into two groups ,recursively sort seach group, and merges them into a final sorted sequence.
Features:
•Is a comparison based algorithm
•Is a stable algorithm
•Is a perfect example of divide & conquer algorithm design strategy
•It was invented by John Von Neumann
MYSORT(A,p,n)
{
q=n+1;
if (p < q) then
{
mid:= ceil((p + q)/2);
MergeSort(p, mid);
MergeSort(mid + 1, q);
Merge(p, mid, q);
}
}
---------------------------------------------------------------------------------------------------------------------------
Merge(A, low, mid, high)
n1=mid –low + 1
n2=high–mid
for i =1 to n1
do L[i] =A[low + i –1]
for j =1 to n2
do R[j] =A[mid + j]
L[n1+1] = infinity
R[n2+1] = infinity
i = 1
j = 1
for k =low to high
do if L[i] <=R[j]
then A[k] =L[i]
i =i+ 1
elseA[k] =R[j]
j =j+1
---------------------------------------------------------------------------------------------------------------------
TIME COMPLEXITY:
The conquer step of merge-sort consist of merging two sorted sequences ,each with n/2 elements and implemented by means of a doubly linkedlist, takes atmost bn steps, for some constant b.
•Likewise, the basis case (n<2) will take at b most steps.
•Therefore, if we let T(n) denote the running time of merge-sort:
T(n) = b if n<2
=2T(n/2)+bn if n>=2
We can therefore analyze the running time of merge-sort by finding a closed form solutionto the above equation.
–That is, a solution that has T(n) only on the left-hand side.
In the iterative substitution, or “plug-and-chug,” technique, we
iteratively apply the recurrence equation to itself and see if we
can find a pattern:
T(n)=2T(n/2)+bn
=2(2T(n/4))+b(n/2))+bn
=4 T(n/4)+2bn
= 8 T(n/8) +3bn
=16 T(n/16)+4bn
=2^i T(n/2^i)+ibn
Note that base, T(n)=b, case occurs when 2i=n. That is, i = log n.
• So, T(n)=bn + bnlogn
• Thus, T(n) is O(n log n).
SPACE COMPLEXITY
IN THIS SORT 2 NEW ARRAYS ARE USED WHICH WILL OCCUPY A SPACE APPROXIMATELY EQUAL TO n SO THE SPACE COMPLEXITY IS O(n)