// The SortingAlgs class that implements insertion sort and iterative merge sort
// your name here

public class SortingAlgs {
    // card comparison
    public int compares(Card c1, Card c2) {
        if (c1.getSuit() < c2.getSuit())
            return -1;
        else if (c1.getSuit() > c2.getSuit())
            return 1;
        else {
            if (c1.getRank() > c2.getRank())
                return 1;
            else if (c1.getRank() < c2.getRank())
                return -1;
            else
                return 0;
        }
    }

    // insertion sort
    public void insertionSort(Card[] cardArray) {
        for (int start = 1; start < cardArray.length; start++) {
            int compare_to = start - 1;
            int current = start;
            while ((compare_to >= 0) && (compares(cardArray[compare_to], cardArray[current]) > 0)) {
                Card temp = cardArray[current];
                cardArray[current] = cardArray[compare_to];
                cardArray[compare_to] = temp;
                current = compare_to;
                compare_to--;

            }
        }
    }

    // merge sort
    public void mergeSort(Card[] cardArray) {
        for (int run_length = 1; run_length <= cardArray.length - 1; run_length *= 2) {
            int merged_size = run_length * 2;
            for (int first = 0; first < cardArray.length - 1; first += merged_size) {
                int mid = first + run_length - 1;
                if (mid > cardArray.length - 1)
                    mid = cardArray.length - 1;

                int last;
                if (first + merged_size < cardArray.length) {
                    last = first + merged_size - 1;
                }

                else
                    last = cardArray.length - 1;
                merge(cardArray, first, mid, last);
            }
        }
    }

    // merge two sorted arrays into one sorted array
    public void merge(Card[] cardArray, int first, int mid, int last) {
        Card[] aux1 = new Card[mid - first + 1];
        Card[] aux2 = new Card[last - mid];

        for (int i = 0; i < aux1.length; i++)
            aux1[i] = cardArray[i + first];
        for (int i = 0; i < aux2.length; i++)
            aux2[i] = cardArray[i + mid + 1];

        int main_index = first;
        int l_index = 0;
        int r_index = 0;

        while ((l_index < aux1.length) && (r_index < aux2.length)) {
            if (compares(aux1[l_index], aux2[r_index]) <= 0) {
                cardArray[main_index] = aux1[l_index];
                l_index++;
            }
            else {
                cardArray[main_index] = aux2[r_index];
                r_index++;
            }
            main_index++;
        }
        for (l_index = l_index; l_index < aux1.length; l_index++) {
            cardArray[main_index] = aux1[l_index];
            main_index++;
        }

        for (r_index = r_index; r_index < aux2.length; r_index++) {
            cardArray[main_index] = aux2[r_index];
            main_index++;
        }

    }
}