Algorithm (Lab report 05)

Theory: The merge sort is very important to sorting algorithm. It can sort different two (Arrays) elements with Divide, conquer and combine approach. Merge sort is very predictable. It makes between 0.5*lg(n) and lg(n) comparisons per element, and between lg(n) and 1.5*lg(n) swaps per element. The minima are achieved for already sorted data; the maxima are achieved, on average, for random data. If using Θ(n) extra space is of no concern, then merge sort is an excellent choice: It is simple to implement, and it is the only stable O(n·lg(n)) sorting algorithm. Note that when sorting linked lists, merge sort requires only Θ(lg(n)) extra space (for recursion).

Apparatus:

           i.   Computer.

          ii.   Coding Language.

         iii.   Compiler (Code block, Dev c/c++, Turbo c/c++ etc.)

         iv.   Coding skill.

Algorithm: (Computational (MERGE-SORT(A,p,q,r)

Step01:  if p <r

Step02:   then q ← (r + p)/2

Step03:   MERGE-SORT(A, p, q )

Step04:   MERGE-SORT(A,q+1,r)

Step05:   MERGE(A, p, q, r)
Step06:    n1←q-p+1

Step07:    n2←r-q

Step08:    create arrays L[1...N1+1] and R[1...N2+1]

Step09:    for i←1 to N1

Step10:   do L[i] ← A[p+i-1]

Step11:   for j ← 1 to n2

Step12:   do R[j] ← A[q+j]

Step13:   L[N1+1] ← ∞

Step14:   R[N2+1] ← ∞

Step15:   i ← 1

Step16:   j ← 1

Step17:   for k ← p to r

Step18:   do if L[i] ≤ R[j]

Step19:   then A[k] ← L[i]

Step20:   i ← i+1

Step21:   else A[k] ← R[j]

Step22:    j ← j+1

Source code 01: (Random merge sort)
#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include<time.h>
#include<stdlib.h>
#define max 5000

void MergeSort(int low, int high);
void Merge(int low, int mid , int high);

int a[max];
int b[max];
int low=0;
int high;

int main(void)
{
char check='y';
int i,n;
clock_t start, finish;
while(check=='y')
  {
  textmode(C80);
  cout<<"How many number do you generate(Merge sort):";
  cin>>n;
  for(i=0; i<n; i++)
    {
    a[i]=random(n);
    }
  start=clock();
  high=n;
  for(i=0; i<n; i++)
    {
    MergeSort(low,high);
    cout<<a[i]<<"\t";
    }
  finish=clock();
  cout<<"\nTotal time is:"<<(finish-start)/CLK_TCK<<" second";         check=getche();
}
return 0;
}

void MergeSort(int low, int high)
{
int mid;
if(low<high)
  {
  mid=(low+high)/2;
  MergeSort(low, mid);
  MergeSort(mid+1,high);
  Merge(low, mid, high);
  }
}

void Merge(int low, int mid, int high)
{
int h,i,j,k;
h=low;
i=low;
j=mid+1;
while((h<=mid)&&(j<=high))
  {
  if(a[h]<=a[j])
    {
    b[i]=a[h];
    h=h+1;
    }
  else
    {
    b[i]=a[j];
    j=j+1;
    }
  i=i+1;
  }
if(h>mid)
  {
  for(k=j; k<=high; k++)
    {
    b[i]=a[k];
    i=i+1;
    }
  }
else
  {
  for(k=h; k<=mid; k++)
    {
    b[i]=a[k];
    i=i+1;
    }
  }
for(k=low; k<=high; k++)
a[k]=b[k];
}                                                            Result:

Sample Input 01:
How many number do you generate(Merge sort): 10

Sample Output 01:
0          0          0          0          1          2          3          3          5          7
Total time is 0 second.

===========================================================

Sample Input 02:
How many number do you generate(Merge sort): 14

Sample Output 02:
0          0          0          0          1          2          3          3          4          4          6          7          9
9
Total time is 0 second.

Caution: You must change this code. And also change the test value when you print it......Try to make change or modify this.