import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import javax.swing.JOptionPane;

/**
 *
 * @author Bill Kraynek
 */
public class ArrayListSorts {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        long t1;
        long t2;
        int size = 100;
        ArrayList<Integer> list1 = new ArrayList<Integer>();
        ArrayList<Integer> list2 = new ArrayList<Integer>();
        ArrayList<Integer> list3 = new ArrayList<Integer>();
        int[] array1 = new int[size];
        int[] array2 = new int[size];
        int[] array3 = new int[size];
        Random random = new Random();
        for (int i = 0; i < size; i++) {
            int number = random.nextInt(10000000);
            list1.add(number);
            list2.add(number);
            list3.add(number);
            array1[i] = number;
            array2[i] = number;
            array3[i] = number;
        }// end for
        String times = "";
        JOptionPane.showMessageDialog(null, list1);
        t1 = System.currentTimeMillis();
        iSortList(list1);
        t2 = System.currentTimeMillis();
        times += "Recursive insertion sort with ArrayLists took " + (t2 - t1) + " milliseconds\n";
        t1 = System.currentTimeMillis();
        bSortList(list2);
        t2 = System.currentTimeMillis();
        times += "Recursive bubble sort with ArrayLists took " + (t2 - t1) + " milliseconds\n";
        t1 = System.currentTimeMillis();
        mSortList(list3);
        t2 = System.currentTimeMillis();
        times += "Recursive merge sort with ArrayLists took " + (t2 - t1) + " milliseconds\n";
        t1 = System.currentTimeMillis();
        sortArray(array1);
        t2 = System.currentTimeMillis();
        times += "Recursive insertion sort with Arrays took " + (t2 - t1) + " milliseconds\n";
        t1 = System.currentTimeMillis();
        mergeSort(array2);
        t2 = System.currentTimeMillis();
        times += "Recursive merge sort with Arrays took " + (t2 - t1) + " milliseconds\n";
        t1 = System.currentTimeMillis();
        insertionSort(array3);
        t2 = System.currentTimeMillis();
        times += "Iterative insertion sort with Arrays took " + (t2 - t1) + " milliseconds\n";
        JOptionPane.showMessageDialog(null, times);
        JOptionPane.showMessageDialog(null, list1 + "\n" + list2 + "\n"+ list3 + "\n"+ Arrays.toString(array1) + "\n" + Arrays.toString(array2) + "\n" + Arrays.toString(array3));
    }// end

    public static void iSortList(List<Integer> list) {
        if (list.size() == 1) {
            return;
        }
        iSortList(list.subList(0, list.size() - 1));
        int last = list.get(list.size() - 1);
        int i = list.size() - 2;
        while (i >= 0 && list.get(i) > last) {
            list.set(i + 1, list.get(i));
            i--;
        }// end while
        list.set(i + 1, last);
    }// end

    public static void bSortList(List<Integer> list) {
        if (list.size() == 1) {
            return;
        }
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i) > list.get(i + 1)) {
                int hold = list.get(i);
                list.set(i, list.get(i + 1));
                list.set(i + 1, hold);
            }// end if
        }// end for
        bSortList(list.subList(0, list.size() - 1));
    }// end

    public static void mSortList(List<Integer> list) {
        if (list.size() <= 1) {
            return;
        }
        int middle = list.size() / 2;
        mSortList(list.subList(0, middle));
        mSortList(list.subList(middle, list.size()));
        ArrayList<Integer> bList = new ArrayList<Integer>();
        int l = 0;
        int r = middle;
        while (l < middle && r < list.size()) {
            if (list.get(l) <= list.get(r)) {
                bList.add(list.get(l++));
            } else {
                bList.add(list.get(r++));
            } // end if/else
        } // end while
        while (l < middle) {
            bList.add(list.get(l++));
        }
        while (r < list.size()) {
            bList.add(list.get(r++));
        }
        list.clear();
        for (int x : bList) {
            list.add(x);
        }

    }

    public static void sortArray(int[] array) {
        sortArray(array, array.length - 1);
    }// end

    public static void sortArray(int[] array, int end) {
        if (end == 0) {
            return;
        }
        sortArray(array, end - 1);
        int last = array[end];
        int i = end - 1;
        while (i >= 0 && array[i] > last) {
            array[i + 1] = array[i];
            i--;
        }// end while
        array[i + 1] = last;
    }// end

    public static void insertionSort(int[] array) {
        insertionSort(array, array.length - 1);
    } // end insertionSort

    public static void insertionSort(int[] array, int end) {
        for (int i = 0; i <= end; i++) {
            int hold = array[i];
            int j = i - 1;
            while (j >= 0 && array[j] > hold) {
                array[j + 1] = array[j];
                j--;
            } // end for
            array[j + 1] = hold;
        } // end for
    } // end insertionSort

    public static void mergeSort(int[] array) {
        mergeSort(array, 0, array.length - 1);
    } // end mergeSort

    public static void mergeSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int middle = (left + right) / 2;
        mergeSort(array, left, middle);
        mergeSort(array, middle + 1, right);
        ArrayList<Integer> b = new ArrayList<Integer>();
        int l = left;
        int r = middle + 1;
        int i = 0;
        while (l <= middle && r <= right) {
            if (array[l] <= array[r]) {
                b.add(array[l++]);
            } else {
                b.add(array[r++]);
            } // end if/else
        } // end while
        while (l <= middle) {
            b.add(array[l++]);
        }
        while (r <= right) {
            b.add(array[r++]);
        }
        i = left;
        for (int j = 0; j < b.size(); j++) {
            array[i++] = b.get(j);
        }
    } // end mergeSort
}