"""Mergesort implementation in arrays
CSCI 204 demonstration
Xiannong Meng
2017 fall"""

from array204 import Array

def mergesort_array( the_seq ):
    """A wrapper function for the recursive version of the mergesort()"""
    n = len(the_seq)
    tmp_array = Array(n)

    mergesort( the_seq, 0, n-1, tmp_array )
    return the_seq

def mergesort( the_seq, first, last, tmp_array ):
    """
    Mergesort recursively divide the list into half, sort both halves
    and then merge the two sorted lists into one.
    """
    # If the aList is size 0 or 1, it's already sorted.
    if first == last:   # base case
        return
    else:
        mid = (first + last) // 2

        # Recursively sort the left and right halves
        mergesort( the_seq, first, mid, tmp_array )
        mergesort( the_seq, mid+1, last, tmp_array )
        
        # Merge the two (each sorted) parts back together
        merge_seq( the_seq, first, mid+1, last, tmp_array )
                          
def merge_seq( the_seq, left, right, end, tmp_array ):
    """
    Merge to sorted list, indexed [left:right] and [right:end], 
    into one sorted list.    """

    a = left
    b = right
    m = 0
    # Repeatedly move the smallest of left and right to the new list
    while a < right and b <= end:
        if the_seq[a] < the_seq[b]:
            tmp_array[m] = the_seq[a]
            a += 1
        else:
            tmp_array[m] = the_seq[b]
            b += 1
        m += 1

    # There will only be elements left in one of the original two lists.

    # Append the remains of left (..end) on to the new list.
    while a < right:
        tmp_array[m] = the_seq[a]
        a += 1
        m += 1
         
    # Append the remains of right (rt..end) on to the new list.
    while b <= end:
        tmp_array[m] = the_seq[b]
        b += 1
        m += 1

    # Copy the entire tmp_array back to proper portion in the_seq
    for i in range( end-left+1 ):
        the_seq[i+left] = tmp_array[i]

    return the_seq