public class BigOComplexity {
    
    public static float[] run(){

        // create an empty array with 5000 elements
        int[] arr1 = new int[5000];
        int[] arr2 = new int[5000];
        int[] arr3 = new int[5000];
        int[] arr4 = new int[5000];

        // initialize the arrays
        for (int i = 0; i < arr1.length; i++) {
            arr1[i] = (int) (Math.random() * 10000);
        }

        // signature: arraycopy(Object source_arr, int sourcePos, Object dest_arr, int destPos, int len)
        System.arraycopy(arr1, 0, arr2, 0, 5000);
        System.arraycopy(arr1, 0, arr3, 0, 5000);
        System.arraycopy(arr1, 0, arr4, 0, 5000);

        float[] timeInterval = new float[4];

        // sort the array
        long start = System.currentTimeMillis();
        bubbleSort(arr1);
        long end = System.currentTimeMillis();
        System.out.println("    Bubble Sort: " + (end - start) + "ms");
        timeInterval[0] = (end - start);

        start = System.currentTimeMillis();
        mergeSort(arr2, 0, arr2.length-1);
        end = System.currentTimeMillis();
        System.out.println("    Merge Sort: " + (end - start) + "ms");
        timeInterval[1] = (end - start);

        start = System.currentTimeMillis();
        selectionSort(arr3);
        end = System.currentTimeMillis();
        System.out.println("    Selection Sort: " + (end - start) + "ms");
        timeInterval[2] = (end - start);

        start = System.currentTimeMillis();
        insertionSort(arr4);
        end = System.currentTimeMillis();
        System.out.println("    Insertion Sort: " + (end - start) + "ms");
        timeInterval[3] = (end - start);

        return timeInterval;
    }

    // code from GeeksforGeeks
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    // code from GeeksforGeeks
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int current = arr[i];
            int j = i - 1;
            while (j >= 0 && current < arr[j]) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = current;
        }
    }

    // code from GeeksforGeeks
    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    // code from ChatGPT
    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];
        
        for (int i = 0; i < n1; i++) {
            leftArr[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            rightArr[j] = arr[mid + 1 + j];
        }
        
        int i = 0;
        int j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i];
                i++;
            } else {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }
        
        while (i < n1) {
            arr[k] = leftArr[i];
            i++;
            k++;
        }
        
        while (j < n2) {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }
    
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    
}

public static void main (String[] args) {
    float[] meanTimeInterval = new float[4];

    for (int i = 0; i < 12; i++) {
        System.out.println("Iteration " + i);
        float[] timeInterval = BigOComplexity.run();
        
        for (int j = 0; j < 4; j++) {
            meanTimeInterval[j] += timeInterval[j];
        }
    }

    for (int i = 0; i < 4; i++) {
        meanTimeInterval[i] /= 12;
    }

    // printing average values
    System.out.println("Average Values ");
    System.out.println("    Bubble Sort: " +meanTimeInterval[0] + "ms");
    System.out.println("    Merge Sort: " +meanTimeInterval[1] + "ms");
    System.out.println("    Selection Sort: " +meanTimeInterval[2] + "ms");
    System.out.println("    Insertion Sort: " +meanTimeInterval[3] + "ms");
}

main(null);