In: Computer Science
Complete code in java:-
import java.util.Random;
import java.util.Scanner;
import java.io.*;
class MergeSort {
// These are methods provided by you for sorting the input
array
// Below method is driver method.
public static void mergeSort(int[] arr){
mergeSortRec(arr, 0, arr.length-1);
}
// This is the main function to sort the array.
private static void mergeSortRec(int[] arr, int first, int
last){
if(first<last){
// Partition the array into two equal halves
int mid=(first+last)/2;
// Calling this function recurrsively for both the halves.
mergeSortRec(arr, first, mid);
mergeSortRec(arr, mid+1,last);
// Finally merging the two sorted halves.
merge(arr, first, mid, mid+1, last);
}
}
// This function will merge the 2 sorted halves and make a
sorted array.
private static void merge(int[] arr, int leftFirst,
int leftLast, int rightFirst, int rightLast){
int[] aux=new int[arr.length];
//extra space, this is downside of this algorithm
int index=leftFirst;
int saveFirst=leftFirst;
// From here, this code is merging 2 sorted halves into
one.
while(leftFirst<=leftLast && rightFirst
<=rightLast){
if(arr[leftFirst]<=arr[rightFirst]){
aux[index++]=arr[leftFirst++];
}else{
aux[index++]=arr[rightFirst++];
}
}
while(leftFirst<=leftLast){
aux[index++]=arr[leftFirst++];
}
while(rightFirst<=rightLast)
aux[index++]=arr[rightFirst++];
for(index=saveFirst; index<=rightLast; index++)
arr[index]=aux[index];
}
// Main method
public static void main(String ... args) {
// Creating object for random number generation.
Random rand = new Random();
// Creating Scanner object for taking user input
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a = sc.nextInt();
int b = sc.nextInt();
// Creating array of size 'n'.
int arr[] = new int[n];
// Storing numbers into array in range 'a'-'b'
for(int i = 0; i < n; i++) {
arr[i] = rand.nextInt((b-a)+1)+a;
}
// Here we measuring time before starting mergeSort
method.
long start = System.currentTimeMillis();
mergeSort(arr);
// Again measuring time before starting mergeSort method.
long end = System.currentTimeMillis();
// Priting desired output.
System.out.println("Time taken to sort "+n+ " numbers : " + (end -
start) + "ms");
}
}
Screenshot of output:-
Mege sort uses divide and conquer technique, every time it divides array into 2 almost equal halves and merge this halves into one sorted subarray. Its average case time complexity is O(n*log(n)).