In Java:

Perform the Insertion Sort and Merge Sort algorithm by editing/modifiying the below code and filling in the the missing code. In short discuss the time performance of both algorithms (compare). Please make sure the program works (I use Eclipse). Thank you.

--------------------------------------------------------------------------------------------------------------------------------------------------------------

package sort;

import java.util.*;

public class Sort {

public static int[] insertion_sort (int[] array) {

return array;

/*

* fill in your program

*/

}

public static int[] merge_sort (int[] array, int p, int r) {

/*

* fill in your program

*/

return array;

}

public static int[] merge (int[] array, int p, int q, int r) {

/*

* fill in your program

*/

return array;

}

/*

* n: the size of the output array

*/

public static int[] generate_random_array (int n) {

List list;

int[] array;

list = new ArrayList ();

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

list.add(new Integer(i));

Collections.shuffle(list, new Random(System.currentTimeMillis()));

array = new int[n];

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

array[i] = list.get(i).intValue();

return array;

}

/*

* Input: an integer array

* Output: true if the array is acsendingly sorted, otherwise return false

*/

public static boolean check_sorted (int[] array) {

for (int i = 1; i < array.length; i++) {

if (array[i-1] > array[i])

return false;

}

return true;

}

public static void print_array (int[] array) {

for (int i = 0; i < array.length; i++)

System.out.print(array[i] + ", ");

System.out.println();

}

public static void main(String[] args) {

// TODO Auto-generated method stub

System.out.println("Insertion sort starts ------------------");

for (int n = 10; n <= 100000; n=n*2) {

int[] array = Sort.generate_random_array(n);

long t1 = System.currentTimeMillis();

array = Sort.insertion_sort(array);

long t2 = System.currentTimeMillis();

long t = t2 - t1;

boolean flag = Sort.check_sorted(array);

System.out.println(n + "," + t + "," + flag);

}

System.out.println("Insertion sort ends ------------------");

System.out.println("Merge sort starts ------------------");

for (int n = 10; n <= 100000; n=n*2) {

int[] array = Sort.generate_random_array(n);

long t1 = System.currentTimeMillis();

array = Sort.merge_sort(array, 1, n);

long t2 = System.currentTimeMillis();

long t = t2 - t1;

boolean flag = Sort.check_sorted(array);

System.out.println(n + "," + t + "," + flag);

}

System.out.println("Merge sort ends ------------------");

}

}