"""
YOU:
Implement a bottom-up iterative mergesort that is allowed a scratch space of size n/2 rounded down, 
where n is the length of the array to be sorted. Give your answer in python.

CHATGPT:
To implement a bottom-up iterative merge sort that uses a scratch space of size 
floor(n/2) (where n is the length of the array), we need to modify the traditional
merge sort algorithm. The bottom-up merge sort iteratively merges pairs of adjacent 
subarrays of increasing sizes, rather than dividing the array recursively.

In this modified version, we use a scratch space (an auxiliary array) of size 
floor(n/2) to store half of the elements during the merge phase, which requires 
careful management of indices. Here's how we can do it:

1. Create a scratch space of size floor(n/2)
2. For each round, iterate over the array in steps of 2*s where s
   starts from 1 and doubles each time until it exceeds n
3. In each iteration, merge subarrays of size s using the scratch space. This involves:
   * Copying the first half of the elements to be merged into the scratch space.
   * Merging back into the original array by comparing elements from the scratch space 
     and the second half in the original array.

Here's the Python implementation of this approach:
"""


def mergesort1(arr, scratch):
    n = len(arr)
    # Assume scratch has size n // 2

    size = 1
    while size < n:
        for start in range(0, n, 2 * size):
            mid = min(start + size, n)
            end = min(start + 2 * size, n)

            # Copy first half to scratch space
            for i in range(start, mid):
                scratch[i - start] = arr[i]

            # Merge back to arr
            i, j, k = 0, mid, start
            while i < size and j < end:
                if scratch[i] <= arr[j]:
                    arr[k] = scratch[i]
                    i += 1
                else:
                    arr[k] = arr[j]
                    j += 1
                k += 1

            # Copy any remaining elements from scratch space
            while i < size and k < end:
                arr[k] = scratch[i]
                i += 1
                k += 1

        size *= 2

    return arr


"""
YOU:
This code crashes with an IndexError.

CHATGPT:
You're right, and I apologize for the oversight. The issue arises because the size 
variable can exceed the length of the scratch array when copying elements. 

To modify the code so that it uses an auxiliary array of size floor(n/2), we need 
to adjust how we handle the merge operation. Since the auxiliary array will only 
be able to hold half of the elements (rounded down), we need to be careful with 
the indices and the ranges of elements being merged. The idea is to always use 
the auxiliary array for the smaller half of the subarrays being merged.

Here's the updated implementation:
"""

def mergesort2(arr, scratch):
    """
    Perform bottom-up merge sort on the array using smaller auxiliary space.
    Assume the scratch space has size floor(n/2).
    """
    n = len(arr)
 
    # For current size of subarrays to be merged, curr_size varies from 1 to n/2
    curr_size = 1
    while curr_size < n:
        for left_start in range(0, n - curr_size, 2 * curr_size):
            mid = left_start + curr_size - 1
            right_end = min(left_start + 2 * curr_size - 1, n - 1)

            # Using smaller auxiliary array for merging
            merge_with_smaller_aux(arr, scratch, left_start, mid, right_end)

        curr_size *= 2


def merge_with_smaller_aux(arr, aux, left_start, mid, right_end):
    """
    Merge two halves of an array using a smaller auxiliary space.
    """
    # Determine the smaller half and copy it to the auxiliary array
    if mid - left_start <= right_end - mid:
        aux_size = mid - left_start
        for i in range(aux_size):
            aux[i] = arr[left_start + i]
        i, j, k = 0, mid + 1, left_start
    else:
        aux_size = right_end - mid
        for i in range(aux_size):
            aux[i] = arr[mid + 1 + i]
        i, j, k = 0, left_start, mid + 1

    # Merge the temp arrays back into arr
    while i < aux_size and j <= right_end:
        if aux[i] <= arr[j]:
            arr[k] = aux[i]
            i += 1
        else:
            arr[k] = arr[j]
            j += 1
        k += 1

    # Copy the remaining elements of aux, if any
    while i < aux_size:
        arr[k] = aux[i]
        i += 1
        k += 1

"""
YOU:
Oh ChatGPT, you are quite useless. First, it isn't necessary to test which half is smaller,
since it's always the right half. Second, your merging routine is dumb. You need to merge
from the right, not the left, in order to avoid overwriting the values that are in the left
half. I'll have better luck asking Cambridge students to write the code!
"""