# cython: language_level=3

"""Module provides a mergesort.  Requires 2n memory."""

import insertionsort

def mergesort(list_):
    """Convenient wrapper for our worker merge sort routine."""
    length = `len'(list_)
    # Just give us a preallocated list of the correct length.  We don't really care about the values.
    help_list = list(range(length))
    mergesort_c(list_, help_list, length)

ifdef(`m4pyx',c)def mergesort_c(ifdef(`m4pyx',list )list_, ifdef(`m4pyx',list )help_list, ifdef(`m4pyx',unsigned int )size):
    """merge sort algorithm."""
ifdef(`m4pyx',`    cdef list source_list')
ifdef(`m4pyx',`    cdef list dest_list')
ifdef(`m4pyx',`    cdef unsigned int sublist_size')
ifdef(`m4pyx',`    cdef unsigned int dest_index')
ifdef(`m4pyx',`    cdef unsigned int sublist_start')
ifdef(`m4pyx',`    cdef unsigned int source_and_dest_index')
ifdef(`m4pyx',`    cdef unsigned int sublist1_index')
ifdef(`m4pyx',`    cdef unsigned int sublist2_index')
ifdef(`m4pyx',`    cdef unsigned int sublist1_end')
ifdef(`m4pyx',`    cdef unsigned int sublist2_end')
ifdef(`m4pyx',`    cdef int need_final_copy')

    source_list = list_
    dest_list = help_list

    need_final_copy = False

    # use insertion sort to get a bunch of sublists sorted initially
    sublist_size = 128
    for sublist_start in range(0, size, sublist_size):
        insertionsort.insertionsort(list_, sublist_start, min(sublist_start + sublist_size - 1, size - 1))

    size_times_2 = size * 2
    # now start merging from (initially) a sublist size of 256...
    while sublist_size < size_times_2:
        sublist_size *= 2
        dest_index = 0
        for sublist_start in range(0, size, sublist_size):
            sublist1_index = sublist_start
            sublist1_end = sublist_start + sublist_size // 2
            if sublist1_end > size:
                sublist1_end = size
            sublist2_index = sublist1_end
            sublist2_end = sublist_start+sublist_size
            if(sublist2_end > size):
                sublist2_end = size
            # merge the two lists until we hit the end of one of them
            while sublist1_index < sublist1_end and sublist2_index < sublist2_end:
                if source_list[sublist1_index] < source_list[sublist2_index]:
                    dest_list[dest_index] = source_list[sublist1_index]
                    dest_index += 1
                    sublist1_index += 1
                else:
                    dest_list[dest_index] = source_list[sublist2_index]
                    dest_index += 1
                    sublist2_index += 1
            # merge list 1 - if it's not already empty
            while sublist1_index < sublist1_end:
                dest_list[dest_index] = source_list[sublist1_index]
                dest_index += 1
                sublist1_index += 1
            # merge list 2 - if it's not already empty
            while sublist2_index < sublist2_end:
                dest_list[dest_index] = source_list[sublist2_index]
                dest_index += 1
                sublist2_index += 1
        # swap the source list and destination list, so we can merge back into the other on the next iteration
        source_list, dest_list = dest_list, source_list
        # and invert the sense of our "need final copy" flag
        need_final_copy = not need_final_copy

    if need_final_copy:
        for source_and_dest_index in range(size):
            list_[source_and_dest_index] = help_list[source_and_dest_index]