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

Answer 1

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)