I'm having a small code to compare the run time between insertion sort and merge sort - somehow merge sort takes a longer time than insertion sort. Did I do something wrong in the sorting process? Insertion sort takes about 5000 milliseconds and merge sort takes about 9000 million seconds...which I actually expect to be the reverse (merge sort time < insertion sort time).
import java.util.*;
public class Main {
private static Random random = new Random();
public static void main(String[] args){
int[] array1 = new int[100000];
int[] array2 = new int[100000];
for(int i = 0; i < 100000; i++){
array1[i] = random.nextInt();
array2[i] = random.nextInt();
}
long startTime_insertion = System.currentTimeMillis();
insertionSort(array1, array1.length);
long endTime_insertion = System.currentTimeMillis();
System.out.println("The insertion sort time is " + (endTime_insertion - startTime_insertion) + " milliseconds.");
long startTime_mergesort = System.currentTimeMillis();
mergesort(array2, 0, array2.length-1);
long endTime_mergesort = System.currentTimeMillis();
System.out.println("The merge sort time is " + (endTime_mergesort - startTime_mergesort) + " milliseconds.");
}
public static void insertionSort(int[] array, int lengthArray) {
int i, j, temp;
int n = lengthArray;
for (i = 1; i < n; i++)
{
temp =array[i];
j = i - 1;
while (j >= 0 && array[j] > temp) {
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = temp;
}
}
public static void mergesort(int[] array, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergesort(array, left, mid);
mergesort(array, mid + 1, right);
int A[] = Arrays.copyOfRange(array, left, mid + 1);
int B[] = Arrays.copyOfRange(array, mid + 1, right + 1);
int mergedArray[] = binaryMerge(A, B, A.length, B.length);
int i = left;
int j = 0;
while (j <= right - left)
array[i++] = mergedArray[j++];
}
}
private static int[] binaryMerge(int A[], int B[], int lengthA, int lengthB) {
int lengthC = lengthA + lengthB;
int C[] = new int[lengthC];
int a = 0, b = 0, c = 0;
while (a < lengthA && b < lengthB) {
if (A[a] < B[b]) {
for (int i = 0; i < lengthA; i++) {
C[c] = A[a];
}
a++;
}
else {
for (int i = 0; i < lengthB; i++) {
C[c] = B[b];
}
b++;
}
c++;
}
while (a < lengthA) {
for (int i = 0; i < lengthA; i++) {
C[c] = A[a];
}
a++;
c++;
}
while(b < lengthB){
for (int i = 0; i < lengthB; i++) {
C[c] = B[b];
}
b++;
c++;
}
return C;
}
}