Consider the following variation of merge sort where the recursive calls are mad
ID: 3710641 • Letter: C
Question
Consider the following variation of merge sort where the recursive calls are made only till the list is “large”; if the list is small, insertion sort is used is used to sort the list.
NewMergeSort(array A)
{
if A has L or fewer elements then InsetionSort(A) else
{
split A into Left and Right;
NewMergeSort(Left); NewMergeSort(Right); Merge Left and Right
}
}
What you have to do in this problem is to see what value of L gives the best results.
1. Consider at least the following values of L: 1, 2, 4, 8, 16, 32, 64.
2. Generate large random arrays (i.e. the values of the arrays are generated using a random number generator)
run NewMergeSort with different values of L and see which value of L yields the fastest result.
Explanation / Answer
Solution:
Note: The java implementation of Mereg with insertion sort is given eblow, please have a look.
code:
package chegg;
import java.util.Random;
public class MergeWithInsertion {
//function to perform insertion sort
void insertSort(int arr[])
{
int vn = arr.length;
for (int vi=1; vi<vn; ++vi)
{
int pivot = arr[vi];
int vj = vi-1;
while (vj>=0 && arr[vj] > pivot)
{
arr[vj+1] = arr[vj];
vj = vj-1;
}
arr[vj+1] = pivot;
}
}
//the merge function
void merge(int arr[], int len, int mer, int rand)
{
int n1 = mer - len + 1;
int n2 = rand - mer;
int Left[] = new int [n1];
int Right[] = new int [n2];
for (int vi=0; vi<n1; ++vi)
Left[vi] = arr[len + vi];
for (int vj=0; vj<n2; ++vj)
Right[vj] = arr[mer + 1+ vj];
int vi = 0, vj = 0;
int vk = len;
while (vi < n1 && vj < n2)
{
if (Left[vi] <= Right[vj])
{
arr[vk] = Left[vi];
vi++;
}
else
{
arr[vk] = Right[vj];
vj++;
}
vk++;
}
while (vi < n1)
{
arr[vk] = Left[vi];
vi++;
vk++;
}
while (vj < n2)
{
arr[vk] = Right[vj];
vj++;
vk++;
}
}
//the function to perform merge sort
void mergeSort(int arr[], int len, int rand)
{
if (len < rand)
{
int mer = (len+rand)/2;
mergeSort(arr, len, mer);
mergeSort(arr , mer+1, rand);
//Merge the sorted halves
merge(arr, len, mer, rand);
}
}
// Driver main method
public static void main(String args[])
{
MergeWithInsertion obj = new MergeWithInsertion();
System.out.println("for 5000 number array");
int[] arr0 = new int[5000];
int[] iarr0 = new int[5000];
Random rand = new Random();
for (int vi = 0; vi < arr0.length; vi++)
{
arr0[vi] = rand.nextInt();
iarr0[vi]=arr0[vi];
}
long startTime = System.nanoTime();
obj.insertSort(arr0);
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println("The insertion sort takes: "+totalTime+" nano sec");
startTime = System.nanoTime();
obj.mergeSort(iarr0, 0, iarr0.length-1);
endTime = System.nanoTime();
totalTime = endTime - startTime;
System.out.println("The merge sort takes: "+totalTime+" nano sec");
System.out.println("for 10000 number array");
int[] arr1 = new int[10000];
int[] iarr1 = new int[10000];
for (int vi = 0; vi < arr1.length; vi++)
{
arr1[vi] = rand.nextInt();
iarr1[vi]=arr1[vi];
}
startTime = System.nanoTime();
obj.insertSort(arr1);
endTime = System.nanoTime();
totalTime = endTime - startTime;
System.out.println("The insertion sort takes: "+totalTime+" nano sec");
startTime = System.nanoTime();
obj.mergeSort(iarr1, 0, iarr1.length-1);
endTime = System.nanoTime();
totalTime = endTime - startTime;
System.out.println("The merge sort takes: "+totalTime+" nano sec");
System.out.println("for 20000 number array");
int[] arr2 = new int[20000];
int[] iarr2 = new int[20000];
for (int vi = 0; vi < arr2.length; vi++)
{
arr2[vi] = rand.nextInt();
iarr2[vi]=arr2[vi];
}
startTime = System.nanoTime();
obj.insertSort(arr2);
endTime = System.nanoTime();
totalTime = endTime - startTime;
System.out.println("The insertion sort takes: "+totalTime+" nano sec");
startTime = System.nanoTime();
obj.mergeSort(iarr2, 0, iarr2.length-1);
endTime = System.nanoTime();
totalTime = endTime - startTime;
System.out.println("The merge sort takes: "+totalTime+" nano sec");
}
}
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)