0

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;
    }
}
DiMario
  • 33
  • 1
  • 8
  • 3
    9000 million seconds? Dang, your program has been running longer than many modern countries. – Abion47 Sep 22 '20 at 20:42
  • Strange...I tested against https://www.tutorialspoint.com/compile_java_online.php and I got 1936 milliseconds for insertion and 6719 milliseconds for merge sort. I think that it is wrong with my code rather than my machine. – DiMario Sep 22 '20 at 20:45
  • 1
    Measuring the performance of anything in Java is hard, and this way of doing it can give you nonsensical answers -- as you've just seen. – Louis Wasserman Sep 22 '20 at 21:10
  • That is true. Thank you for pointing out that. – DiMario Sep 22 '20 at 21:13
  • The array copies and extra conditionals are taking more time. I have example code for both bottom up and top down in [this answer](https://stackoverflow.com/questions/46106922/46107386#46107386). On my system, (Intel 3770K 3.5 ghz, 8 year old cpu, Win 7 Pro 64 bit, netbeans 8.2), it takes 15 milliseconds to sort 100,000 integers. – rcgldr Sep 22 '20 at 22:07

0 Answers0