SortingJun26

class Main {
    
    public static void bubblesort(int[] array1){
        if (array1 ==null){
            return;
        }
        
        // O(n°2=
        for (int index1 = 0; index1 < array1.length; index1++){
            for (int index2= index1+1; index2 <  array1.length; index2++){
                if (array1[index1]< array1[index2]){
                    int tmp = array1[index1];
                    array1[index1] = array1[index2];
                    array1[index2] = tmp;
                }
                if (array1[index1]> array1[index2]){
                    int tmp = array1[index1];
                    array1[index1] = array1[index2];
                    array1[index2] = tmp;
                }
            }
        }
    }
    
    public static int[] mergeSort(int array[]){
        if (array.length == 1){
            return array;
        }
        
        // 0 1 2 3 4 5 6 7 8 9
        // 5
        // 0 1 2 3 4 5 6 7 8
        // 
        int leftSize = 0;
        int rightSize = 0;
        if ( array.length % 2 == 0 ){
            leftSize= array.length /2;
            rightSize= array.length /2;
        } else {
            leftSize= array.length /2+1;
            rightSize= array.length /2;
        }
        
        
        
        System.out.println("length:"+array.length+" leftSize:"+ leftSize+" rightSize:"+rightSize);
        
        int left[] = new int[leftSize];
        int right[] = new int[rightSize];
        
        fill(left, array, 0);
        fill(right, array, rightSize);
        
        printAll(left);
        printAll(right);
        
        return merge(mergeSort(left), mergeSort(right));
    }
    
    public static void fill(int []emptyArray, int[] sourceArray, int start){
        for (int i=0; i < emptyArray.length; i++){
            emptyArray[i]= sourceArray[start+i];
        }
    }
    
    public static int[] merge(int left[], int right[]){
        int mergedArray[] = new int[left.length+right.length]; 
        int leftIndex=0, rightIndex=0, mergedIndex=0;
        
        while (leftIndex < left.length && rightIndex < right.length){
            if (left[leftIndex] <= right[rightIndex]){
                mergedArray[mergedIndex++] = left[leftIndex++];
            } else if (left[leftIndex] >= right[rightIndex]){
                mergedArray[mergedIndex++] = right[rightIndex++];
            }
        }
        
        while (left.length > leftIndex){
            mergedArray[mergedIndex++] = left[leftIndex++];
        }
        while (right.length > rightIndex){
            mergedArray[mergedIndex++] = right[rightIndex++];
        }
        
        return mergedArray;
    }
    
    
    
    // array            8 9 7 6 5 4 3 2 1 0
    // index =          0 1
    // index2 =         1 2
    // smallestIndex =  0
    public static void selectionSort(int [] unsortedArray){
        if (unsortedArray == null || unsortedArray.length == 1){
            System.out.println("");
        }
        
        int smallestNumberIndex=0;
        
        for (int index=0; index < unsortedArray.length; index ++){
            for (int index2=index+1; index2 < unsortedArray.length; index2 ++){
                if (unsortedArray[index2] < unsortedArray[smallestNumberIndex]){
                    smallestNumberIndex = index2;
                }
            }
            swap (unsortedArray, index, smallestNumberIndex);
            smallestNumberIndex= index+1;
        }
        
    }
    
    public static void insertionSort(int[] halfSortedArray){
        for (int currentIndex=1; currentIndex < halfSortedArray.length; currentIndex ++){
            int lastSorted =currentIndex;
            
            while (lastSorted > 0 && halfSortedArray[lastSorted] < halfSortedArray[lastSorted-1]){
                swap(halfSortedArray, lastSorted, lastSorted-1);
                lastSorted--;
            }
        }
    }
    
    public static void swap(int[] array, int currentIndex, int smallestNumberIndex){
        int tmp= array[currentIndex];
        array[currentIndex] = array[smallestNumberIndex];
        array[smallestNumberIndex] = tmp;
    }
    
    public static void printAll(int array[]){
        System.out.println(" ");
        for (int i=0; i < array.length; i++){
            System.out.print(array[i]+ " ");
        }
    }
    
    public static void main(String[] args) {
        int array[] = new int[10];
        
        array[0] = 9;
        array[1] = 8;
        array[2] = 7;
        array[3] = 6;
        array[4] = 5;
        array[5] = 4;
        array[6] = 3;
        array[7] = 2;
        array[8] = 1;
        array[9] = 0;
        mergeSort(array);
        printAll(array);
        
    }
}