import javax.swing.*;
import java.util.*;

/**
 * Three examples of sorting algorithms
 * insert sort, bubble sort and merge sort
 */

public class SortingAlgorithms {

    // The array to sort
    private int[] a;
    // A copy of the original array
    private int [] initialArray;
    // Default dimension of a
    private static final int SIZE=10;

    /**
     * Generate an array of random integers of size SIZE
     */
    public SortingAlgorithms()
    {
        // Use the other constructor
    }

    /**
     * Generate an array of random integers of size n
     */
    public SortingAlgorithms(int n)
    {
        // Take the default size if n <=0

        // Create a

        // Fill a with random integers (between 0 and 999)

        // Initialize initialArray and make a copy of a in initialArray
        // (use System.arraycopy)
    }

    /**
     * write the array as a String
     * (toString is automatically called when using print
     *  with a SortingAlgorithms)
     */
    public String toString()
    {
    }

    /**
     * Sort the array with insert sort
     */
    public void insertSort()
    {
    }

    /**
     * Precondition: a is ordered from 0 to i-1
     * Postcondition: a is ordered from 0 to i
     */
    private void insert(int i)
    {
    }
    /**
     * Sort the array with bubble sort
     */
    public void bubbleSort()
    {
    }

    /**
     * Sort the array with merge sort (a faster algorithm)
     */
    public void mergeSort()
    {
    }

    /**
     * Divide the array in two
     * Order each part
     * Merge the two ordered parts
     */
    private void divideInTwo(int first, int last)
    {
        if (first<last)
        {
            // Midpoint

            // Sort a[first,...,mid] (using divideInTwo)

            // Sort a[mid+1,...,last] (using divideInTwo)

            // Merge sorted halves
        }
    //	else
            // Base case: nothing to do
    }

    /**
     * Precondition: first<=mid<=last
     *               a[first,...,mid] is sorted in increasing order
     *               a[mid+1,...,last] is sorted in increasing order
     * Postcondition a[first,...,last] is sorted in increasing order
     */
    private void merge(int first, int mid, int last)
    {

        // Method: copy the two halves in a temp array in increasing order
        //         copy temp back in a

        // Allocate a temp array on the heap
        // temp must be big enough to receive the two halves of A

        // Index for temp
        int index = 0;

        // Start and end of the first half
        int first1=first;
        int last1 = mid;
        // Start and end of the second half
        int first2 = mid+1;
        int last2 = last;

        // Copy the two halves in temp (in increasing order)

        // Anything left in the first half

        // Anything left in the second half

        // Copy temp in a
    }

    /**
     * Test the Sorting algorithm class
     */
    public static void main(String[] args)
    {
        while(true)
        {
            int n = Integer.parseInt(JOptionPane.showInputDialog(null,
            "Enter the size of the array (<=0 to stop)"));
            if (n<=0) break;

            // Create a SortingAlgorithms with an array of size n

            // Print the array before sorting

            // Test insert sort
            // Clock time just before the call

            // sort with insert sort

            // Clock time after the call

            // Print the execution time and the array after sorting
            System.out.println("With insert sort:");

            // Test bubble sort (on the same array)
            // copy initialArray in a

            // Clock time just before the call

            // call bubble sort

            // Clock time after the call

            // Print the execution time and the array after sorting
            System.out.println("With bubble sort:");

            // Test merge sort (on the same array)

            // Clock time just before the call
            // use System.currentTimeMillis()


            // sort with mergeSort

            // Clock time after the call

            // Print the execution time and the array after sorting
            System.out.println("With merge sort:");

            // Compare with the Java API
            // Make an arrayList and copy a in it

            // Clock time just before the call

            // Sort with Collections.sort

            // Clock time after the call

            // Print the execution time and the list after sorting
            System.out.println("With a sort from the Collections class:");

        }
        // Terminate the application properly
        System.exit(0);
    }
}