Sort a given set of n integer elements using Merge Sort method and compute its time complexity

0 like 0 dislike
531 views

Sort a given set of n integer elements using Merge Sort method and compute its time complexity. Run the program for varied values of n> 5000, and record the time taken to sort. The elements can be read from a file or can be generated using the random number generator. Demonstrate using Java how the divide-and-conquer method works along with its time complexity analysis: worst case,average case and best case.

For Indian Students- INR 570/- || For International Students- \$12.99/-

S.No.

Course Name

Apply Coupon

1.

Tensorflow 2 & Keras:Deep Learning & Artificial Intelligence

Apply Coupon

2.

Computer Vision with OpenCV | Deep Learning CNN Projects

Apply Coupon

3.

Complete Machine Learning & Data Science with Python Apply Coupon

4.

Natural Language Processing-NLP with Deep Learning in Python Apply Coupon

5.

Computer Vision OpenCV Python | YOLO| Deep Learning in Colab Apply Coupon

6.

Complete Python Programming from scratch with Projects Apply Coupon

0 like 0 dislike
by Goeduhub's Expert (5.8k points)

Java Program

import java.util.Random;

import java.util.Scanner;

public class MergeSort

{

public static void main(String[] args)

{

int a[]= new int[100000];

Scanner in = new Scanner(System.in);

long start, end;

System.out.print("Enter the number of elements to be sorted: ");

int n = in.nextInt();

Random rand= new Random();

for(int i=0;i<n;i++)

a[i]=rand.nextInt(2000);

System.out.println("Array elements to be sorted are:");

for(int i=0; i<n; i++)

System.out.println(a[i]);

start=System.nanoTime();

mergesort(a,0,n-1);

end=System.nanoTime();

System.out.println("\nThe sorted elements are: ");

for(int i=0; i<n; i++)

System.out.println(a[i]);

System.out.println("\nThe time taken to sort is "+(end-start)+"ns");

}

static void mergesort(int a[], int low, int high)

{

int mid;

if(low < high)

{

mid = (low+high)/2;

mergesort(a, low, mid);

mergesort(a, mid+1, high);

merge(a, low, mid, high);

}

}

static void merge(int a[], int low, int mid, int high)

{

int i, j, h, k, b[]= new int[100000];

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];

}

}

Output

Value of n = 5100

Random 5100 numbers will be generated

...........