import java.util.*;

public class SortComparison { 
    // bubble sort
    public static void bubbleSort(int array[]) { 
        boolean sorted = false; 
        int passes = 0;
        while (!sorted) {
            sorted = true; 
            passes++;
            for (int i = 0; i < (array.length - passes); i++) {
                if (array[i] > array[i + 1]) {
                    int temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                    sorted = false;
                }
            }            
        }
    }

    // merge sort
    public static void mergeSort(int array[], int start, int end) {
        if(start < end) {
            int middle = (start + end) / 2;

            // sort left half
            mergeSort(array, start, middle);

            // sort right half
            mergeSort(array, middle + 1, end);

            // merge the two halves
            merge(array, start, end);
        }
    }

    // the merge function used in merge sort
    public static void merge(int array[], int start, int end) {
        int middle = (start + end) / 2;
        int temp_index = 0;

        // create a temporary array
        int temp [] = new int[end - start + 1];

        // merge in sorted data from the 2 halves
        int left = start;
        int right = middle + 1;

        // while both halves have data
        while((left <= middle) && (right <= end)) {
            // if the left half value is less than right
            if (array[left] < array[right]) {
                // take from left
                temp[temp_index] = array[left];
                temp_index++;
                left++;
            }
            else {
                // take from right
                temp[temp_index] = array[right];
                temp_index++;
                right++;
            }
        }

        // add the remaining elements from the left half
        while(left <= middle) {
            temp[temp_index] = array[left];
            temp_index++;
            left++;
        }

        // add the remaining elements from the right half
        while(right <= end) {
            temp[temp_index] = array[right];
            temp_index++;
            right++;
        }

        // move from temp array to the original array
        for(int i = start; i <= end; i++) {
            array[i] = temp[i - start];
        }
    }


    public static void main(String args[]) {
        // TODO test both sorts for the numbers
        // 7500, 15000, 22500, 30000, 37500, 45000, 52500, 60000, 67500, and 75000
    }
}