****JAVA****FILL IN PROGRAM****

package sorting;

import java.util.*;

public class Sort {

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

//

}

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

//fill in program //

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

{

//fill in program//

}

//* * n: the size of the output array *

//k: the maximum value in the array *//

public static int[] generate_random_array (int n, int k) {

List list;

int[] array;

Random rnd;

rnd = new Random(System.currentTimeMillis());

list = new ArrayList ();

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

list.add(new Integer(rnd.nextInt(k+1)));

Collections.shuffle(list, rnd);

array = new int[n];

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

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

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;

list.add(new Integer(i));

Collections.shuffle(list, new

Random(System.currentTimeMillis()));

array = new int[n];

for (int i = 0; i < n

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

int k = 100;

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 ------------------");

}

}