## Algorithm Description:
For this algorithm, a function called Stooge Sort has been devised. If the array has only two elements, it swaps them if they are out of order. If the array has more than two elements, it will recursively sort the first 2/3 of the array, then recursively sort the last 2/3 of the array, then finally recursively sorts the first 2/3 of the array again.

fun StoogeSort(A, 0, n) {
    if (n = 2 and A[0]>A[1]) {
        swap(A,0,1);
    }
    else if (n > 2) {
        m = ceil(2n/3);
        StoogeSort(A,0,m);
        StoogeSort(A,n-m,n);
        StoogeSort(A,0,m);
    }
}

## a) Correctness Proof:
Goal: The function stoogeSort(A,0,n) correctly sorts the array.

We will use Proof by Induction on the size of the array.

## Base Cases:
- If ```n = 2 and A[0]>A[1]```, the values will swap. This is because we want the array to be sorted in ascending order.
- If ```n = 2 and A[0]<=A[1]```, the values don't need to sort, as they are already in their correct order.

## Induction Hypothesis:
Assume that for any array of length n, StoogeSort will correctly sort the array.

## Inductive Step: n > 2
Let ```m = ceil(2n/3)```

1. The first m elements: A[0:m]
2. The last m elements: A[n-m:n]
3. The first m elements again: A[0:m]

This works because we first sort the first 2/3 of the Array and then sort the last 2/3 of the array. The issue is that we now have a middle overlap inside of our array that is not correctly sorted. Because of this, we need to sort the first 2/3 of the Array again to correctly sort the middle overlap.

By induction, since each recursive call sorts its portions correctly, and the overlap is taken care of, the entire Array A[0:n] is sorted.

## b) Reccurence for Time Complexity T(n)
State a recurrence for the time complexity T(n) of StoogeSort. Ignore the ceil in your recurrence. Solve the recurrence.

If n <= 2: The time complexity is Θ(1)
If n > 2: The time complexity is 3T(2n/3) + Θ(1)
This is because we call the recursive function 3 times that sorts two thirds of the array.

## Master Theorem
T(n) = aT(n/b) + f(n)
a = 3
b = 3/2
This is because we want to make the formula:

Thus,

Next Step:

Since ln(3) = 1.099 and ln(3/2) = .405

This means that: