#include <iostream>
#include <string>
using namespace std;

bool isSorted(int *a, int n)
{
    bool sorted = true;
    int count = 0;
    while (count < n - 1)
    {
        if (a[count] > a[count + 1])
            sorted = false;
        count++;
    }
    return sorted;
}

void insertionSort(int *a, int n)
{
    int temp, j;
    for (int i = 0; i < n; i++)
    {
        j = i;
        //While J is greater than 0 AND an element is less than the one before it
        while (j > 0 && a[j] < a[j - 1])
        {
            //If true swap and decrease the value of j to check again
            temp = a[j];
            a[j] = a[j - 1];
            a[j - 1] = temp;
            //Decreasing the value of j is used
            j--;
        }
    }
}

void quickSort(int *a, int left, int right)
{
    /* partitioning */
    //Half way between the ranges
    int mid = ((left + right) / 2);
    //Lowest value
    int low = left;
    //Highest value
    int high = right;
    //Pivot point is the middle value in the array
    int pivot = a[mid];

    int tmp = -1;
    //While lowest value is less than or equal to highest value
    while (low <= high)
    {
        //while the first value in the array is less than the pivot point, check the next element
        while (a[low] < pivot){ low++; };
        //while the highest value is higher than the pivot point, move to the next highest
        while (a[high] > pivot){ high--; };
        //If the lowest element is less than or qual to the highest, swap the values
        if (low <= high)
        {
            //swap
            tmp = a[low];
            a[low] = a[high];
            a[high] = tmp;
            low++; high--;
        }
    }
    /* end partitioning */
    if (left < high) quickSort(a, left, high);
    if (low < right) quickSort(a, low, right);

}
void merging(int *a, int first, int mid, int last)
{
    int l1, l2, i;
    int b[500]; // Length of array

    for (l1 = first, l2 = mid + 1, i = first; l1 <= mid && l2 <= last; i++)
    {
        if (a[l1] <= a[l2]) { b[i] = a[l1++]; }
        else { b[i] = a[l2++]; }
    }
    while (l1 <= mid) { b[i++] = a[l1++]; }
    while (l2 <= last) { b[i++] = a[l2++]; }

    for (i = first; i <= last; i++)
        a[i] = b[i];

}

void mergeSort(int *a, int first, int last)
{
    int mid = ((first + last) / 2);

    if (first < last)
    {

        mergeSort(a, first, mid);
        mergeSort(a, mid + 1, last);
        merging(a, first, mid, last);
    }
}

int main()
{
    //Out of order test
    int a[] = { 15, 20, 23, 18, 30 };
    if (isSorted(a, 5) == true)
        cout << "A: The array is sorted" << endl;
    else
        cout << "A: The array is not sorted" << endl;
    //In order test
    int b[] = { 15, 20, 23, 28, 30 };
    if (isSorted(b, 5) == true)
        cout << "B: The array is sorted" << endl;
    else
        cout << "B: The array is not sorted" << endl;
    int c[] = { 5, 4, 7, 2, 6, 1, 3 };
    if (isSorted(c, 7) == true)
        cout << "C: The array is sorted" << endl;
    else
        cout << "C: The array is not sorted" << endl;
    insertionSort(c, 7);
    if (isSorted(c, 7) == true)
        cout << "C: The array is sorted" << endl;
    else
        cout << "C: The array is not sorted" << endl;

    int d[] = { 5, 4, 7, 2, 6, 1, 3 };
    if (isSorted(d, 7) == true)
        cout << "D: The array is sorted" << endl;
    else
        cout << "D: The array is not sorted" << endl;
    quickSort(d, 0,6);
    if (isSorted(d, 7) == true)
        cout << "D: The array is sorted" << endl;
    else
        cout << "D: The array is not sorted" << endl;

    int e[] = { 5, 4, 7, 2, 6, 1, 3 };
    if (isSorted(e, 7) == true)
        cout << "E: The array is sorted" << endl;
    else
        cout << "E: The array is not sorted" << endl;
    quickSort(e, 0, 6);
    if (isSorted(e, 7) == true)
        cout << "E: The array is sorted" << endl;
    else
        cout << "E: The array is not sorted" << endl;
    return 0;
}