"""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)
    mergesort( the_seq, 0, n-1 )
    return the_seq

def mergesort( the_seq, first, last ):
    """
    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 )
        mergesort( the_seq, mid+1, last )
        
        # Merge the two (each sorted) parts back together
        merge_seq( the_seq, first, mid, last )
                          
def merge_seq( the_seq, left, right, end ):
    """
    Merge to sorted list, indexed [left:right] and [right:end], 
    into one sorted list.    """
    n_left  = right-left+1
    n_right = end-right
    arr_left = Array(n_left)
    arr_right = Array(n_right)
    
    
    # copy the two halfs of the array into temp
    for i in range(n_left):
        arr_left[i] = the_seq[i+left]
 
    print_array(arr_left, n_left)
    
    for i in range(n_right):
        arr_right[i]= the_seq[i+right+1]

    print_array(arr_right, n_right)
        
    i = 0
    j = 0
    m = 0
    # Repeatedly move the smallest of left and right to the new list
    while i < n_left and j < n_right:
        if arr_left[i] < arr_right[j]:
            the_seq[m] = arr_left[i]
            i += 1
        else:
            the_seq[m] = arr_right[j]
            j +=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 i < n_left:
        the_seq[m] = arr_left[i]
        i += 1
        m += 1
         
    # Append the remains of right (rt..end) on to the new list.
    while j < n_right:
        the_seq[m] = arr_right[j]
        j += 1
        m += 1


    return the_seq


def print_array(seq, n):
    print('[', end = '')
    for i in range(n):
        print(seq[i], ',', end = '')
    print(']')