class SortMethods {
    public SortMethods() {

    }
    public int[] bubbleSort(int[] array) {
        for(int i = 0; i<array.length; i++) {
            for( int j = 1; j<array.length - i; j++) {
                if (array[j] < array[j-1]) {
                    int value = array[j];
                    array[j] = array[j-1];
                    array[j-1] = value;
                }
            }
        }
        return array;
    }
    public int[] selectionSort(int[] array) {
        for(int i = 0; i<array.length; i++) {
            Integer minimum = Integer.MAX_VALUE;
            int minimumIndex = 0;
            for( int j = i + 1; j<array.length; j++) {
                if (array[j] < minimum) {
                    minimum = array[j];
                    minimumIndex = j;
                }
            }
            int value = array[i];
            if (minimum < value) {
                array[i] = array[minimumIndex];
                array[minimumIndex] = value;
            }
        }
        return array;
    }
    public int[] insertionSort(int[] array) {
        for (int i = 1; i<array.length; i++) {
            int value = array[i];
            int index = 0;
            for (int j = i - 1; j >= 0; j--) {
                if (value < array[j]) {
                    array[j+1] = array[j];
                } else {
                    index = j + 1;
                    break;
                }
                if (j == 0) {
                    index = j;
                }
            }
            array[index] = value;
        }
        return array;
    }
    public void mergeSort(int[] a, int n) {
        if (n < 2) {
            return;
        }
        int mid = n / 2;
        int[] l = new int[mid];
        int[] r = new int[n - mid];
    
        for (int i = 0; i < mid; i++) {
            l[i] = a[i];
        }
        for (int i = mid; i < n; i++) {
            r[i - mid] = a[i];
        }
        this.mergeSort(l, mid);
        this.mergeSort(r, n - mid);
    
        this.merge(a, l, r, mid, n - mid);
    }
    public void merge(int[] a, int[] l, int[] r, int left, int right) {
    
        int i = 0, j = 0, k = 0;
        while (i < left && j < right) {
            if (l[i] <= r[j]) {
                a[k++] = l[i++];
            }
            else {
                a[k++] = r[j++];
            }
        }
        while (i < left) {
            a[k++] = l[i++];
        }
        while (j < right) {
            a[k++] = r[j++];
        }
    }
}

class SortTester {
    public static void test() {
        SortMethods sorter = new SortMethods();
        int[] array = {14, 12, 18, 20, 2};
        int[] bubbleSorted = sorter.bubbleSort(array);
        for(int i = 0; i < bubbleSorted.length; i++) {
            System.out.print(bubbleSorted[i]);
            System.out.print(",");
        }
        System.out.println();
        int[] array2 = {14, 12, 18, 20, 2};
        int[] selectionSorted = sorter.selectionSort(array2);
        for(int i = 0; i < selectionSorted.length; i++) {
            System.out.print(selectionSorted[i]);
            System.out.print(",");
        }
        System.out.println();
        int[] array3 = {8, 10, 9, 2, 1};
        int[] insertionSorted = sorter.insertionSort(array3);
        for(int i = 0; i < insertionSorted.length; i++) {
            System.out.print(insertionSorted[i]);
            System.out.print(",");
        }
        System.out.println();
        int[] array4 = {1, 2, 8, 9, 10};
        // sorter.mergeSort(array4);
        for(int i = 0; i < array4.length; i++) {
            System.out.print(array4[i]);
            System.out.print(",");
        }
        System.out.println();
    }
}
SortTester.test();

2,12,14,18,20,
2,12,14,18,20,
1,2,8,9,10,
1,2,8,9,10,