JAVA: fill in the rest for insertion sort:

based on the follwoing:

INSERTION-SORT.A/

1 for j D 2 to A:length

2 keyDAj

3 // Insert Aj into the sorted sequence A1 : : j 1 .

4 iDj 1

5 whilei >0andAi >key

6 Ai C 1 D Ai

7 iDi 1

8 AiC1 Dkey

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

*/

int q;

if (p < r){

q = (p + r)/2;

Sort.merge_sort(array, p, q);

Sort.merge_sort(array, q+1, r);

array = Sort.merge(array, p, q, r);

}

return array;

}

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

/*

* fill in your program

*/

int n1, n2, i, j, k;

int[] L, R;

n1 = q - p +1;

n2 = r - q;

L = new int[n1+1];

R = new int[n2+1];

for (i = 0; i < n1; i++)

L[i] = array[p+i];

for (j = 0; j < n2; j++)

R[j] = array[q+1+j];

L[n1] = Integer.MAX_VALUE;

R[n2] = Integer.MAX_VALUE;

i = 0;

j = 0;

for (k = p; k <= r; k++) {

if (L[i] <= R[j]){

i++;

}

else {

array [k] = R[j];

j++;

}

}

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, 0, n-1);

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

}

}